【题目链接】:

【题意】

两个人轮流玩游戏;

取序列中的前k(k>1)个数字,拿出来;

把这k个数字全部加起来合成一个数字;

再把这个新的数字放在序列的开头;

新合成的数字是这个人这轮游戏获得的分数;

一直玩直到只剩下一个数字为止;

把每一个人的分数统计出来;

问最后,第一个人比第二个人的分数高,最多能高出多少.

【题解】

每次玩完一轮游戏之后,

另外一个人取第j个；

实际上还是取原序列的前j个数的和;

设

f[i][0]表示前i个数字都合在一起了,然后当前轮到第一个人玩,第一个人比第二个人高出的分数;

f[i][1]表示前i个数字都合在一起了,然后当前轮到第二个人玩,第一个人比第二个人高出的分数;

(为负数就表示第二个人比第一个人的分数高)

显然,第二个人玩的时候,必然想让f值变小;

而第一个人玩的时候,必然想让f值变大;

则根据这个逆推

f[i][0]=max(f[j][1]+sum[j]),i<j<=n

f[i][1]=min(f[j][0]−sum[j]),i<j<=n

因为第二个人取的时候是让f值变小的,所以是减去sum[j],然后取最小值就是了;

这里可以O(1)维护i+1..n这个范围里面f[i][1]+sum[j]的最大值,f[i][0]-sum[j]的最小值;

所以复杂度能做到O(N);

最后输出f[1][0]就是了;

(即前1个数合在了一起,然后到第一个人取,第一个人比第二个人高出的最大分数);

【Number Of WA】

0

【完整代码】

#include 
     
      using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define ms(x,y) memset(x,y,sizeof x)typedef pair
      
        pii;typedef pair
       
         pll;const int dx[9] = {
    0,1,-1,0,0,-1,-1,1,1};const int dy[9] = {
    0,0,0,-1,1,-1,1,-1,1};const double pi = acos(-1.0);const int N = 2e5+100;int n,a[N];LL sum[N],dp[N][2],ma1,mi0;int main(){    //freopen("F:\\rush.txt","r",stdin);    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use    //init??????    cin >> n;    rep1(i,1,n) cin >> a[i];    rep1(i,1,n)        sum[i] = sum[i-1]+a[i];    dp[N][0] = dp[N][1] = 0;    ma1 = dp[n][1] + sum[n],mi0 = dp[n][0]-sum[n];    rep2(i,n-1,1)    {        dp[i][0] = ma1;        dp[i][1] = mi0;        if (dp[i][0]-sum[i]
        
         ma1)            ma1 = dp[i][1]+sum[i];    }    cout << dp[1][0] << endl;    return 0;}