建设网站用什么软件排版,网站建设人才有哪些,应聘网站运营建设面试,佛山网站公司建设网站目录 取数游戏题目描述背景输入输出数据范围 题解解法优化 打赏 取数游戏
题目描述
背景
两人将 n n n个正整数围成一个圆环#xff0c;规则如下#xff1a;
第一名玩家随意选取数字#xff1b;第二名玩家从与第一名玩家相邻的两个数字中选择一个#xff1b;而后依次在… 目录 取数游戏题目描述背景输入输出数据范围 题解解法优化 打赏 取数游戏
题目描述
背景
两人将 n n n个正整数围成一个圆环规则如下
第一名玩家随意选取数字第二名玩家从与第一名玩家相邻的两个数字中选择一个而后依次在到目前为止所取的任何数字旁边取一个数字直到数字用完选择更多奇数的玩家获胜 第一个选取数字的玩家想知道他能做出多少不同的第一步使他有机会获胜
输入
第一行一个整数 n n n第二行 n n n个整数 n u m i num_i numi表示围在地上的数字
输出
输出一个整数表示有机会获胜的不同的第一步的数量
数据范围 1 ≤ n ≤ 100 , 1 ≤ n u m i ≤ 1000 1 \le n \le 100 , 1 \le num_i \le 1000 1≤n≤100,1≤numi≤1000
题解
解法
由于要算的是有机会获胜的不同第一步的数量所以对于每个可能的第一步只要后续所有选择情况中第一名玩家获得最多奇数的那一种情况下超过了第二名玩家即可 为此可以定义一个二维数组 f [ ] [ ] f[][] f[][] f [ i ] [ j ] f[i][j] f[i][j]表示在第 i i i至 j j j个数已经被选择后 i i i可以大于 j j j直到所有数都被选择该过程中第一名得到的奇数最多可超出第二名多少 使用动态规划来更新这个数组先由大到小枚举已经被选的数的数量 i ( n − 1 ≥ i ≥ 1 ) i(n - 1 \ge i \ge 1) i(n−1≥i≥1)再枚举被选数的区间定义变量 l , r l , r l,r表示枚举到的区间的左右边界下标变量 l l , r r ll , rr ll,rr分别表示表示圆环中 l l l的前一个数和 r r r的后一个数再根据 i 1 i 1 i1的奇偶判断接下来是第一名还是第二名玩家选数这样就得到了状态转移方程 f [ l ] [ r ] m a x ( f [ l l ] [ r ] ± n u m [ l l ] % 2 , f [ l ] [ r r ] ± n u m [ r r ] % 2 ) f[l][r] max(f[ll][r] \pm num[ll] \% 2 , f[l][rr] \pm num[rr] \% 2) f[l][r]max(f[ll][r]±num[ll]%2,f[l][rr]±num[rr]%2) i 1 i 1 i1为奇时取 反之取 − - − 全部更新完后统计满足 f [ i ] [ i ] n u m [ i ] % 2 0 f[i][i] num[i] \% 2 0 f[i][i]num[i]%20因为第一个数一定是第一名玩家选的的 i i i有几个即可 代码如下
#includecstdio#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 ] num[i] num[i]的奇偶性所以可以在输入时就把 n u m [ i ] num[i] num[i]处理成 0 0 0或 1 1 1这样 n u m [ ] num[] num[]只需要为 b o o l bool bool数组 代码如下
#includecstdio#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;
}打赏
制作不易若有帮助欢迎打赏
