uva10891 Game of Sum(博弈论+dp)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=11&problem=1832&mosmsg=Submission+received+with+ID+13415943

感觉博弈题写的很纠结。。。

这题换了几种姿势，首先双方都是足够聪明的，那么他们一定让自己的优势都足够大。

那么我们用DP(l,r)来表示先手能得到的最大分差，那么ans=max(当前选手选择的得分-在他后面的作为先手的最大分差)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define ll long long
 5 using namespace std;
 6 int n;
 7 ll a[110],sum[110][110];
 8 void read(){
 9     for(int i=0;i<n;i++) scanf("%lld",&a[i]);
10 }
11 ll dp[110][110];
12 ll solve(int l,int r){
13     if(l>r) return 0;
14     if(l==r) return a[l];
15     if(dp[l][r]!=-(ll)1e18) return dp[l][r];
16     ll tmp,ret=-(ll)1e18;
17     for(int i=l;i<=r;i++){
18         tmp=solve(l,i-1);
19         if(sum[i][r]-tmp>ret){
20             ret=-tmp+sum[i][r];
21         }
22     }
23     for(int i=l;i<=r;i++){
24         tmp=solve(i+1,r);
25         if(sum[l][i]-tmp>ret){
26             ret=-tmp+sum[l][i];
27         }
28     }
29     //cout<<l<<" "<<r<<" "<<ret<<endl;
30     return dp[l][r]=ret;
31 }
32 void gao(){
33     for(int i=0;i<n;i++){
34         sum[i][i]=a[i];
35         for(int j=i+1;j<n;j++) sum[i][j]=sum[i][j-1]+a[j];
36     }
37     for(int i=0;i<110;i++){
38         for(int j=0;j<110;j++){
39             dp[i][j]=-(ll)1e18;
40         }
41     }
42     printf("%lld
",solve(0,n-1));
43 }
44 
45 int main(){
46     while(~scanf("%d",&n)&&n){
47         read();
48         gao();
49     }
50     return 0;
51 }

uva10891