原题目链接
赢球票
题目描述
某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。
主持人拿出 N 张卡片（上面写着 1 到 N 的数字），打乱顺序，排成一个圆圈。
你可以从任意一张卡片开始顺时针数数：1, 2, 3, …
- 如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中；
- 从下一个卡片重新从 1 开始数；
- 直到无法再收获任何卡片为止，游戏结束。
囊中卡片数字的和，就是你赢得的球票张数。
示例说明
- 卡片排列是：
1 2 3
从第 1 张卡开始数：
第 1 次数到 1，对应卡片是 1 → 拿走
第 2 次从卡片 2 开始数，但1 ≠ 2→ 失败，游戏结束
最多可得 1 张球票 - 卡片排列是：
2 1 3
从第 2 张卡开始：
第 1 次数到 1，卡片是 1 → 拿走
第 2 次从卡片 3 开始数，数到 1, 2，卡片是 3 → 拿走
最后一张也是 2 → 拿走
可以全部拿到，得 6 张球票（2+1+3）
输入格式
- 第一行：一个整数
N（N ≤ 100），表示卡片数目。 - 第二行：
N个整数，表示顺时针排列的卡片。
输出格式
- 输出一行，一个整数，表示最好情况下能赢得的球票总数。
输入样例
3
1 2 3
输出样例
1
c++代码
#include<bits/stdc++.h>using namespace std;int N;
int arr[100], know[100];
int cont = 0, ans = 0;void dfs(int i, int j) {if (i == N) {ans = max(ans, cont + arr[j]);return;}int recoder = 1;for (int k = j;recoder <= N;k++) {if (k == N) k = 0;if (know[k] == 0) continue;if (recoder == arr[k]) {cont += recoder, know[k] = 0;ans = max(ans, cont);for (int l = k + 1; ;l++) {if (l == N) l = 0;if (know[l] == 0) continue;dfs(i + 1, l);break;}know[k] = 1, cont -= recoder;break;}recoder++;}
}int main() {cin >> N;for (int i = 0; i < N; i++) cin >> arr[i];for (int i = 0; i < N; i++) know[i] = 1;for (int i = 0; i < N; i++) dfs(1, i);cout << ans;return 0;
}//by wqs
算法思路
暴力dfs题，枚举第一张牌选哪个。
注意用know标记哪些牌被选过了，我们要选下一张没有被标记过的牌，不能直接去选下一张。
