当前位置：首页 > news >正文

小美和大富翁

news 2024/11/5 20:25:58

牛客网题目链接，第四题

小美在玩《大富翁》游戏，游戏中有 n+1 个城市排成一排，编号从 0 到 n ，第 i 个城市上有一个数字 ai，表示到达第
i 个城市可以获得 ai 枚金币。
每一轮开始时小美会获得四张卡牌，分别可以跳跃 1、2、3、4 个城市，例如小美可以从城市1跳跃 3 个城市到达城市4。当小美使用完这 4 张卡牌后，会开启新的一轮。

初始时，小美拥有 0 枚金币，在任意时刻，小美的金币数量都必须大于等于 0 ，
小美想知道她从第 0 个城市出发，到达第 n 个城市最多可以获得多少枚金币。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
,第一行输入一个整数 n\ (1 <= n <= 10^5) 表示城市个数。
,第二行输入 n 个整数 a1,a2,…,an (-10^9 <= ai <= 10^9) 表示到达城市1到n可以获得的金币数量（第0个城市无法获得金币）。
输出描述：
,在一行上输出一个整数表示答案；如果无法到达第 n 个城市，则输出 -1 。
示例1
输入例子：
10
-1 2 3 4 -9 -9 -1 3 -1 -1
输出例子：
9
例子说明：
最优的方法是：
第 1 步：使用跳跃 3 的卡牌，从 0 跳到 3 ，获得 3 枚金币；
第 2 步：使用跳跃 1 的卡牌，从 3 跳到 4 ，获得 4 枚金币，共有 7 枚金币；
第 3 步：使用跳跃 4 的卡牌，从 4 跳到 8 ，获得 3 枚金币，共有 10 枚金币；
第 4 步：使用跳跃 2 的卡牌，从 8 跳到 10 ，获得 -1 枚金币，共有 9 枚金币。

20个用例，最后一个没通过，有哪位好心人，帮我看看错哪了，我看一整天了

#include<stdio.h>
#include<string.h>void printArr(int *a, int len) {for (int i = 0; i < len; i++){printf("%d ", a[i]);}printf("\n");    
}void getComb(int n, int combs[][n]) {int chose[n];int chosen[n+1];int index = 0;int i = 1;int index_c = 0;memset(chose, 0, sizeof(chose));memset(chosen, 0, sizeof(chosen));while (index >= 0){i = chose[index] + 1;while (i < n+1)   // 选一个数{if (chosen[i] == 0) {break;}i++;}if (i == n+1) {   // 无可选，回退chosen[chose[index]] = 0;chose[index] = 0;index--;continue;}chosen[chose[index]] = 0;   // 选择新数前，释放老数chose[index] = i;chosen[i] = 1;index++;if (index == n) {// printArr(chose, n);memcpy(combs[index_c++], chose, sizeof(chose));chosen[i] = 0;index--;}}
}long long getSocre(int *arr, int choice[4], int len, int *legal) {long long score = 0;arr--;  //初始位置不在arr[0]。。在arr[-1]int *end = arr + len;*legal = 1;for (int i = 0; arr != end; i++){arr += choice[i];if (arr > end) {*legal = 0;  //代表不是正确路径，无法到达n，返回的-1无效return -1;}score += *arr;}return score;
}//在任意时刻，小美的金币数量都必须大于等于 0
long long maxSocre(int arr[], int len) {int combiantions[4*3*2][4] = {0};getComb(4, combiantions);// printArr(combiantions[3], 4);long long totalSocre = 0;long long maxSocre = 0;int legal = 1;for (int j=0; j<(len-1)/10 + 1; j++) {int x = 10;if (len - j*10 < x) {x = len - j*10;}int first = 1;for (int i=0; i<4*3*2; i++) {long long score = getSocre(arr+j*10, combiantions[i], x, &legal);if (!legal) {continue;}// printf("%d  ", first);if (first) {maxSocre = score;first = 0;}if (maxSocre < score) {maxSocre = score;}}totalSocre += maxSocre;if (totalSocre < 0) {return -1;}}return totalSocre;
}int main(int argc, char const *argv[])
{int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++){scanf("%d", &arr[i]);}// printArr(arr, n);long long socre = maxSocre(arr, n);printf("%lld\n", socre);return 0;
}