题目链接
题意：
两个人分n个物品，每个物品都有权值，最初特殊卡在先手手里。
对于每一回合，玩家可以选择一个物品给自己，然后将特殊卡传给对手。问最后先手和后手获得的权值分别是多少，两者都采取最优策略。
思路：
跟上题类似的思路，记录dp[i]表示当前回合操作的玩家能够获得的最大权值，那么dp[1]就是先手能够获得的最大权值，总权值和减去dp[1]就是后手能够获得的最大权值。所以从n倒推过去就能得到答案。
dp[i]可以从dp[i+1]过程转移过来，如果玩家在上一回合里就留下卡牌，当前回合的值就还是dp[i+1]；如果玩家A在上一回合里给出卡牌，那么dp[i+1]就表示玩家B在第i+1回合里获得的最大权值，那么sum-dp[i+1]就表示玩家A在第i+1回合里获得的最大权值，其中sum表示i+1到n的物品权值之和，所以此种操作下玩家A能够获得的最大权值是sum-dp[i+1]+a[i];
代码：
///#pragma GCC optimize(3) ///#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") ///#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") ///#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") ///#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll 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; } char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f,mod=1e9+7; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=2000+100,N=1e6+7; const double PI = atan(1.0)*4; const double eps=1e-6; ll dp[2100]; ll n,a[2100]; ll sum[2100]; int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=n;i;i--){ sum[i]=sum[i+1]+a[i]; dp[i]=max(dp[i+1],sum[i+1]-dp[i+1]+a[i]); } cout<<sum[1]-dp[1]<<" "<<dp[1]<<endl; return 0; }
