[文章目录]
Description
n个数，两个人轮流取数，保证取的位置递增，每个人要使自己取的数的和尽量大，求两个人都在最优策略下取的和各是多少。并且在自身所得的和不影响的情况下可以让另一个人所得的和更大一点。问两人所得的和。n<=700000
我们可以从后向前推。设f[i],g[i]为数列为i~n的时候所得答案。转移：
f[i]=max(f[i+1~n],w[i]+g[i+1])。设先手选的为now位置的数那么g[i]=g[now+1]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
ll w[701000],f[701000],g[701000];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",w+i);
int now=n; f[n]=w[n];
for(int i=n-1;i;--i)
{
if(w[i]+g[i+1]>=f[now]) now=i,f[i]=w[i]+g[i+1];
else f[i]=f[now];
g[i]=f[now+1];
}
printf("%lld %lld\n",f[1],g[1]);
return 0;
}