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));
     }
     ;
 }
上一篇:变分模态分解(VMD)运算步骤及源码解读


下一篇:习题:codevs 2822 爱在心中 解题报告