A,B两人从序列两端轮流取数,每次可以取多个(甚至取完)
分数为所取数字的和,假设两人足够聪明,求得分差
f[i][j] 区间[i,j] ,先手取得最大得分
转移到取完后对方的序列
f[i][j] = s[i][j] - min{ f[i][k] , f[k2][j] }
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N=104; int vis[N][N],f[N][N]; int a[N],n,s[N]; int dp(int l,int r){ if(vis[l][r]) return f[l][r]; vis[l][r]=1; int k,t=0; for(k=l+1;k<=r;k++) t=min(t,dp(k,r)); for(k=l;k<r;k++) t=min(t,dp(l,k)); f[l][r]=s[r]-s[l-1]-t; return f[l][r]; } int main(){ while(cin>>n,n){ s[0]=0; for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i]; memset(vis,0,sizeof vis); cout<<dp(1,n)*2-s[n]<<endl; } }
标签:int,10891,vis,序列,uva,include From: https://www.cnblogs.com/towboa/p/16833820.html