博弈dp
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <string> 5 using namespace std; 6 7 int d[30][30][30][30]; 8 int visit[30][30][30][30]; 9 int a[50],b[50]; 10 int suma[50],sumb[50]; 11 12 int dfs (int la,int ra,int lb,int rb){ 13 if (d[la][ra][lb][rb]) 14 return d[la][ra][lb][rb]; 15 if (la>ra&&lb>rb) 16 return 0; 17 if (la>ra&&lb==rb){ 18 return d[la][ra][lb][rb]=b[lb]; 19 } 20 if (la==ra&&lb>rb){ 21 return d[la][ra][lb][rb]=a[la]; 22 } 23 int sum=suma[ra]-suma[la-1]+sumb[rb]-sumb[lb-1]; 24 if (la<=ra){ 25 d[la][ra][lb][rb]=max (d[la][ra][lb][rb],sum-dfs (la+1,ra,lb,rb)); 26 d[la][ra][lb][rb]=max (d[la][ra][lb][rb],sum-dfs (la,ra-1,lb,rb)); 27 } 28 if (lb<=rb){ 29 d[la][ra][lb][rb]=max (d[la][ra][lb][rb],sum-dfs (la,ra,lb+1,rb)); 30 d[la][ra][lb][rb]=max (d[la][ra][lb][rb],sum-dfs (la,ra,lb,rb-1)); 31 } 32 return d[la][ra][lb][rb]; 33 } 34 35 int main (){ 36 int t,n; 37 scanf ("%d",&t); 38 while (t--){ 39 cin>>n; 40 suma[0]=0; 41 sumb[0]=0; 42 for (int i=1;i<=n;i++){ 43 scanf ("%d",&a[i]); 44 suma[i]=suma[i-1]+a[i]; 45 } 46 for (int i=1;i<=n;i++){ 47 scanf ("%d",&b[i]); 48 sumb[i]=sumb[i-1]+b[i]; 49 } 50 memset (d,0,sizeof d); 51 dfs (1,n,1,n); 52 cout<<d[1][n][1][n]<<endl; 53 } 54 return 0; 55 }