hdu4597 Play Game DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4597
感觉很不错的区间DP，又做了一遍，感觉自己对边界的处理还是很欠缺
代码：
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 using namespace std;
 6 #define maxn 21
 7 int sum1[maxn];
 8 int sum2[maxn];
 9 int q1[maxn];
10 int q2[maxn];
11 int n;
12 int dp[maxn][maxn][maxn][maxn];
13 int dfs(int s1, int e1,int s2,int e2)
14 {
15     int tmp1,tmp2;
16     int ans;
17    if(s1==0 && s2==0 && e1==0 && e2==0)  return dp[s1][e1][s2][e2]=0;
18    if(dp[s1][e1][s2][e2]>=0)             return dp[s1][e1][s2][e2];
19    if(s1==0 && e1==0 && s2==e2)          return dp[0][0][s2][e2]=q2[s2];
20    if(s1==e1 && s2==0 && e2==0)          return dp[s1][e1][0][0]=q1[s1];
21    if(s1==0 && e1 ==0)            
22    ans=max(q2[s2]+sum2[e2]-sum2[s2]-dfs(0,0,s2+1,e2),q2[e2]+sum2[e2-1]-sum2[s2-1]-dfs(0,0,s2,e2-1));
23    else
24    if(s2==0 && e2 ==0)
25    ans=max(q1[s1]+sum1[e1]-sum1[s1]-dfs(s1+1,e1,0,0),q1[e1]+sum1[e1-1]-sum1[s1-1]-dfs(s1,e1-1,0,0));
26    else
27    if(s1==e1 && s2==e2)
28    ans=max(q1[s1],q2[s2]);
29    else
30    if(s1==e1)
31    {
32       tmp1=max(q2[s2]+sum2[e2]-sum2[s2]+q1[s1]-dfs(s1,e1,s2+1,e2),q2[e2]+sum2[e2-1]-sum2[s2-1]+q1[s1]-dfs(s1,e1,s2,e2-1));
33       tmp2=max(tmp1,q1[s1]+sum2[e2]-sum2[s2-1]-dfs(0,0,s2,e2));
34       ans=max(tmp1,tmp2);
35    }
36    else
37    if(s2==e2)
38    {
39       tmp1=max(q1[s1]+sum1[e1]-sum1[s1]+q2[s2]-dfs(s1+1,e1,s2,e2),q1[e1]+sum1[e1-1]-sum1[s1-1]+q2[s2]-dfs(s1,e1-1,s2,e2));
40       tmp2=max(tmp1,q2[s2]+sum1[e1]-sum1[s1-1]-dfs(s1,e1,0,0));
41       ans=max(tmp1,tmp2);
42    }
43    else
44    {
45    tmp1=max(q1[s1]+sum2[e2]-sum2[s2-1]+sum1[e1]-sum1[s1]-dfs(s1+1,e1,s2,e2),q1[e1]+sum2[e2]-sum2[s2-1]+sum1[e1-1]-sum1[s1-1]-dfs(s1,e1-1,s2,e2));
46    tmp2=max(q2[s2]+sum2[e2]-sum2[s2]+sum1[e1]-sum1[s1-1]-dfs(s1,e1,s2+1,e2),q2[e2]+sum2[e2-1]-sum2[s2-1]+sum1[e1]-sum1[s1-1]-dfs(s1,e1 ,s2,e2-1));
47    ans=max(tmp1,tmp2);
48    }
49    return dp[s1][e1][s2][e2]=ans;
50  }
51 int main()
52 {
53     int t;
54     scanf("%d",&t);
55     while(t--)
56     {
57        scanf("%d",&n);
58        sum1[0]=sum2[0]=0;
59        for(int i=1;i<=n;i++)
60       {
61        scanf("%d",&q1[i]);
62        sum1[i]=sum1[i-1]+q1[i];
63       }
64        for(int i=1;i<=n;i++)
65       { 
66        scanf("%d",&q2[i]);
67        sum2[i]=sum2[i-1]+q2[i];
68       }
69       memset(dp,-1,sizeof(dp));
70       dp[1][n][1][n]=dfs(1,n,1,n);
71       cout<<dp[1][n][1][n]<<endl;
72     }
73     return 0;
74 }