Codeforces #380 738F. Financiers Game
传送门：http://codeforces.com/contest/738/problem/F
题目翻译
两个人轮流取数字求和，若上轮取了(k)个数字，那么本轮只能取(k,k+1)个数字。先手希望和之差尽量大，后手希望小。求最终的和之差。
题解
记忆化搜索
然后就是注意优化空间，通过左右取数之差来作为状态记录标识。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Inf=2100000000; const int Maxn=4000; int n; int dp[Maxn+5][160][80][2]; bool vis[Maxn+5][160][80][2]; int num[Maxn+5]; int DP(int left,int right,int k,int P){ int siz=n-left-right; int delta=right-left+80; if (siz<k) return 0; if (vis[siz][delta][k][P]) return dp[siz][delta][k][P]; vis[siz][delta][k][P]=true; if (P==0) { int t1=-Inf,t2=-Inf; t1=(num[left+k]-num[left])+DP(left+k,right,k,1); if (left+k+1<=n-right) t2=(num[left+k+1]-num[left])+DP(left+k+1,right,k+1,1); dp[siz][delta][k][P]=max(t1,t2); }else { int t1=Inf,t2=Inf; t1=-(num[n-right]-num[n-right-k])+DP(left,right+k,k,0); if (n-right-k>=left+1) t2=-(num[n-right]-num[n-right-k-1])+DP(left,right+k+1,k+1,0); dp[siz][delta][k][P]=min(t1,t2); } return dp[siz][delta][k][P]; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&num[i]); num[i]=num[i]+num[i-1]; } printf("%d\n",DP(0,0,1,0)); return 0; } |
原文链接：Codeforces #380 738F. Financiers Game
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!