[USACO 2009 Nov S]A Coin Game

NC24856. [USACO 2009 Nov S]A Coin Game

描述

Farmer John's cows like to play coin games so FJ has invented with a new two-player coin game called Xoinc for them.
Initially a stack of N (5 <= N <= 2,000) coins sits on the ground; coin i from the top has integer value Ci (1 <= Ci <= 100,000).
The first player starts the game by taking the top one or two coins (C1 and maybe C2) from the stack. If the first player takes just the top coin, the second player may take the following one or two coins in the next turn. If the first player takes two coins then the second player may take the top one, two, three or four coins from the stack. In each turn, the current player must take at least one coin and at most two times the amount of coins last taken by the opposing player. The game is over when there are no more coins to take.
Afterwards, they can use the value of the coins they have taken from the stack to buy treats from FJ, so naturally, their purpose in the game is to maximize the total value of the coins they take. Assuming the second player plays optimally to maximize his own winnings, what is the highest total value that the first player can have when the game is over?

输入描述

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: Ci

输出描述

* Line 1: A single integer representing the maximum value that can be made by the first player.

示例1

输入:

输出:

说明:

There are five coins with the values 1, 3, 1, 7, and 2.
The first player starts by taking a single coin (value 1). The opponent takes one coin as well (value 3). The first player takes two more coins (values 1 and 7 -- total 9). The second player gets the leftover coin (value 2-- total 5).

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 61ms, 内存消耗: 28008K, 提交时间: 2019-08-25 10:37:00

#include<cstdio>
#include<algorithm>
using namespace std;
#define ri register int
int n,a[2005],s[2005],f[2005][2005],maxf[2005][2005];
int main()
{
    scanf("%d",&n);
    for(ri i=1;i<=n;i++)scanf("%d",a+i),s[i]=s[i-1]+a[i];
    for(ri i=n;i;i--)
        for(ri j=1;j<=n-i+1;j++)
        {
            f[i][j]=s[n]-s[i-1]-maxf[i+j][min(j<<1,n-i-j+1)];
            maxf[i][j]=max(maxf[i][j-1],f[i][j]);
        }
    printf("%d",max(f[1][1],f[1][2]));
}

C++11(clang++ 3.9) 解法, 执行用时: 39ms, 内存消耗: 14180K, 提交时间: 2020-04-03 08:49:58

#include<cstdio>
#include<iostream>
using namespace std;
int n,s[2001],f[2001][2001];
int main()
{
	scanf("%d",&n);
	for(int i=n;i;i--)
	scanf("%d",&s[i]);
	for(int i=2;i<=n;i++)
	s[i]+=s[i-1];
	for(int i=1;i<=n;i++)
	for(int j=1;j<=i;j++)
	f[i][j]=max(f[i][j-1],s[i]-f[i-j][min(i-j,j<<1)]);
	printf("%d",f[n][2]);
}

上一题

下一题

详情