出处不详取数游戏

取数游戏

题目描述

背景

两人将 $n$ 个正整数围成一个圆环，规则如下：

第一名玩家随意选取数字；
第二名玩家从与第一名玩家相邻的两个数字中选择一个；
而后依次在到目前为止所取的任何数字旁边取一个数字，直到数字用完，选择更多奇数的玩家获胜
第一个选取数字的玩家想知道他能做出多少不同的第一步，使他有机会获胜

输入

第一行一个整数 $n$ ；
第二行 $n$ 个整数 $num_i$ ，表示围在地上的数字

输出

输出一个整数，表示有机会获胜的不同的第一步的数量

数据范围

$\le n \le 100 , 1 \le num_i \le 1000$

题解

解法

由于要算的是有机会获胜的不同第一步的数量，所以对于每个可能的第一步，只要后续所有选择情况中，第一名玩家获得最多奇数的那一种情况下超过了第二名玩家即可
为此可以定义一个二维数组 $f [] []$ ， $f [i] [j]$ 表示在第 $i$ 至 $j$ 个数已经被选择后（ $i$ 可以大于 $j$ ），直到所有数都被选择，该过程中第一名得到的奇数最多可超出第二名多少
使用动态规划来更新这个数组，先由大到小枚举已经被选的数的数量 $\ge i \ge 1)$ ，再枚举被选数的区间，定义变量 $l, r$ 表示枚举到的区间的左右边界下标，变量 $ll, rr$ 分别表示表示圆环中 $l$ 的前一个数和 $r$ 的后一个数，再根据 $i + 1$ 的奇偶判断接下来是第一名还是第二名玩家选数，这样就得到了状态转移方程： $\pm num[ll] \% 2 , f[l][rr] \pm num[rr] \% 2)$ （ $i + 1$ 为奇时取 $+$ ，反之取 $-$ ）
全部更新完后，统计满足 $\% 2 > 0$ （因为第一个数一定是第一名玩家选的）的 $i$ 有几个即可
代码如下：

#include<cstdio>#define il inlineconst int M = 105;int f[M][M], num[M];int main() {int n, ans = 0;scanf("%d%", &n);for(int i = 1; i <= n; ++i) scanf("%d%", &num[i]);for(int i = n - 1; i >= 1; --i) {if(i % 2 ^ 1)     //等于(i + 1)%2for(int l = 1, r = i; l <= n; ++l) {int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;int s1 = f[ll][r] + num[ll] % 2, s2 = f[l][rr] + num[rr] % 2;f[l][r] = s1 > s2 ? s1 : s2, r = rr;}else for(int l = 1, r = i; l <= n; ++l) {int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;int s1 = f[ll][r] - num[ll] % 2, s2 = f[l][rr] - num[rr] % 2;f[l][r] = s1 < s2 ? s1 : s2, r = rr;}}for(int i = 1; i <= n; ++i) ans += num[i] % 2 + f[i][i] > 0;printf("%d", ans);return 0;
}

优化

可以发现全程只用到了 $n u m [i]$ 的奇偶性，所以可以在输入时就把 $n u m [i]$ 处理成 $0$ 或 $1$ ，这样 $n u m []$ 只需要为 $b oo l$ 数组
代码如下：

#include<cstdio>#define il inlineconst int M = 105;il int read() {int x = 0;char c = getchar();while(c < '0' || c > '9') c = getchar();while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();return x;
}bool num[M];
int f[M][M];int main() {int n = read(), ans = 0;for(int i = 1; i <= n; ++i) num[i] = read() % 2;for(int i = n - 1; i >= 1; --i) {if(i % 2 ^ 1)for(int l = 1, r = i; l <= n; ++l) {int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;int s1 = f[ll][r] + num[ll], s2 = f[l][rr] + num[rr];f[l][r] = s1 > s2 ? s1 : s2, r = rr;}else for(int l = 1, r = i; l <= n; ++l) {int ll = l - 1 ? l - 1 : n, rr = r + 1 <= n ? r + 1 : 1;int s1 = f[ll][r] - num[ll], s2 = f[l][rr] - num[rr];f[l][r] = s1 < s2 ? s1 : s2, r = rr;}}for(int i = 1; i <= n; ++i) ans += num[i] + f[i][i] > 0;printf("%d", ans);return 0;
}