hdu4597 区间dp

 //Accepted    1784 KB    78 ms //区间dp //dp[l1][r1][l2][r2] 表示a数列从l1到r1，b数列从l2到r2能得到的最大分值 // #include <cstdio> #include <cstring> #include <iostream> using namespace std; ; int dp[imax_n][imax_n][imax_n][imax_n]; int n; int a[imax_n],sa[imax_n],b[imax_n],sb[imax_n]; int max(int a,int b) {     return a>b?a:b; } int dfs(int l1,int r1,int l2,int r2) {     ) return dp[l1][r1][l2][r2];     dp[l1][r1][l2][r2]=;     ]+sb[r2]-sb[l2-]-dfs(l1+,r1,l2,r2);     ]+sb[r2]-sb[l2-]-dfs(l1,r1-,l2,r2));     if (l2<=r2)     {         dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sa[r1]-sa[l1-]+sb[r2]-sb[l2-]-dfs(l1,r1,l2+,r2));         dp[l1][r1][l2][r2]=max(dp[l1][r1][l2][r2],sa[r1]-sa[l1-]+sb[r2]-sb[l2-]-dfs(l1,r1,l2,r2-));     }     return dp[l1][r1][l2][r2]; } int main() {     int T;     scanf("%d",&T);     while (T--)     {         scanf("%d",&n);         sa[]=;         ;i<=n;i++)         {             scanf("%d",&a[i]);             sa[i]=sa[i-]+a[i];         }         sb[]=;         ;i<=n;i++)         {             scanf("%d",&b[i]);             sb[i]=sb[i-]+b[i];         }         memset(dp,-,sizeof(dp));         printf(,n,,n));     }     ; }