NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. Description
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. HINT
  • 题解
  • Description

    农夫约翰的奶牛喜欢玩硬币游戏,因此他发明了一种称为“Xoinc”的两人硬币游戏。 初始时,一个有N(5 <= N <= 2,000)枚硬币的堆栈放在地上,从堆顶数起的第I枚硬币的币值为$C_i$ (1 <= $C_i$ <= 100,000)。 开始玩游戏时,第一个玩家可以从堆顶拿走一枚或两枚硬币。如果第一个玩家只拿走堆顶的一枚硬币,那么第二个玩家可以拿走随后的一枚或两枚硬币。如果第一个玩家拿走两枚硬币,则第二个玩家可以拿走1,2,3,或4枚硬币。在每一轮中,当前的玩家至少拿走一枚硬币,至多拿走对手上一次所拿硬币数量的两倍。当没有硬币可拿时,游戏结束。 两个玩家都希望拿到最多钱数的硬币。请问,当游戏结束时,第一个玩家最多能拿多少钱呢?

    Input

    第1行:1个整数N

    第2..N+1行:第i+1行包含1个整数$C_i$

    Output

    第1行:1个整数表示第1个玩家能拿走的最大钱数。

    Sample Input

    1
    2
    3
    4
    5
    6
    5
    1
    3
    1
    7
    2

    Sample Output

    1
    9

    HINT

    样例说明:第1个玩家先取走第1枚,第2个玩家取第2枚;第1个取走第3,4两枚,第2个玩家取走最后1枚。

    题解

    DP

    设f[i][j]为还剩i个硬币这一次最多能取j个的最大价值
    a[i]为硬币价值的后缀和
    为了方便逆序读入
    然后$f[i][j] = max(f[i][j - 1], a[i] - f[i - j][min(i - j, 2 * j)])$
    搞定

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    inline int read()
    {
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
    }
    int a[2005];
    int f[2005][2005];
    int main()
    {
    int n = read();
    for (int i = n; i >= 1; i--) a[i] = read();
    for (int i = 1; i <= n; i++) a[i] += a[i - 1];
    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
    f[i][j] = max(f[i][j - 1], a[i] - f[i - j][min(i - j, j * 2)]);
    printf ("%d\n", f[n][2]);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/01/18/124/

    本文最后更新于 天前,文中所描述的信息可能已发生改变