题目大意就是有一个整数串,有两个人轮流取,每次可以取走一个前缀或后缀。两人都足够聪明,且都会使自己收益最大。求取完后先手比后手多多少。
每次我看见上面那句就会深感自己的愚笨无知。
所以来推推性质?
1.两人取的和是一定的,所以只要先手收益尽量大就可以了,问题转化为求收益尽量大。
2.对于一个区间(l,r),确定了先后手关系,因为两人都足够聪明,所以答案是确定的。
3.因为每次都是从前面或后面取,所以不管怎么取,剩下的一定是一段连续的串。
对于这种两人够聪明但我不聪明的问题,就把聪明丢给状态就可以了。
直接设D(L,R)表示先手在当前串为[l,r]时聪明地选的最大收益。
那么怎么转移呢?先手收益就是总和-后手收益,综合不变,就是要后手收益最小。
因为后手在先手取完后转先手,所以状态转移就出来了。
D(i,j)=Sum(i,j)-min( (D(i+1,j),D(i+2,j),……,D(j,j)) , (D(i,j-1),D(i,j-2),……,D(i,i)) , 0 )。
其中前面是本次从左边取一段,中间是本次从右边取一段,后面是本次取完。
这么写起来可以打记忆搜,复杂度是O(n^3)的,也跑得过去了。
看着上面那个式子很想优化一下?
设 f(i,j)=min(D(i,j),D(i+1,j),……,D(j,j)), g(i,j)=min(D(i,j-1),D(i,j-2),……,D(i,i))。
则D(i,j)=min( min( f(i+1,j),g(i,j-1) ) , 0)。
f和g的转移也很好做。
f(i,j) = min ( f(i+1,j) , D(i,j) ),g(i,j) = min ( g(i,j-1) , D(i,j) )。
于是就可以O(n^2)解决辣。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <complex>
#include <stack>
#define LL long long int
#define dob double
#define FILE "10891"
using namespace std; const int N = ;
int n,f[N][N],g[N][N],D[N][N],S[N]; inline int gi(){
int x=,res=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')res*=-;ch=getchar();}
while(ch<=''&&ch>='')x=x*+ch-,ch=getchar();
return x*res;
} int main()
{
while(n=gi()){
memset(f,,sizeof(f));memset(g,,sizeof(g));
for(int i=;i<=n;++i)
S[i]=S[i-]+(D[i][i]=f[i][i]=g[i][i]=gi());
for(int len=;len<=n;++len)
for(int i=;i<=n;++i){
int j=i+len-;if(j>n)break;
D[i][j]=S[j]-S[i-]-min(,min(f[i+][j],g[i][j-]));
f[i][j]=min(f[i+][j],D[i][j]);
g[i][j]=min(g[i][j-],D[i][j]);
}
printf("%d\n",*D[][n]-(S[n]-S[]));
}
return ;
}
Game of Sum