出处不详 取数游戏

时间:2024-10-01 19:54:33

目录

  • 取数游戏
    • 题目描述
      • 背景
      • 输入
      • 输出
      • 数据范围
    • 题解
      • 解法
      • 优化
    • 打赏

取数游戏

题目描述

背景

两人将 n n n个正整数围成一个圆环,规则如下:

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

输入

  1. 第一行一个整数 n n n
  2. 第二行 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 1n100,1numi1000

题解

解法

由于要算的是有机会获胜的不同第一步的数量,所以对于每个可能的第一步,只要后续所有选择情况中,第一名玩家获得最多奇数的那一种情况下超过了第二名玩家即可
为此可以定义一个二维数组 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(n1i1),再枚举被选数的区间,定义变量 l , r l , r l,r表示枚举到的区间的左右边界下标,变量 l l , r r ll , rr ll,rr分别表示表示圆环中 l l l的前一个数和 r r r的后一个数,再根据 i + 1 i + 1 i+1的奇偶判断接下来是第一名还是第二名玩家选数,这样就得到了状态转移方程: 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 i+1为奇时取 + + +,反之取 − -
全部更新完后,统计满足 f [ i ] [ i ] + n u m [ i ] % 2 > 0 f[i][i] + num[i] \% 2 > 0 f[i][i]+num[i]%2>0(因为第一个数一定是第一名玩家选的)的 i i i有几个即可
代码如下:

#include<cstdio>

#define il inline

const 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)%2
            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;
            }
        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数组
代码如下:

#include<cstdio>

#define il inline

const 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;
}

打赏

制作不易,若有帮助,欢迎打赏!
赞赏码

支付宝付款码