//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)); } ; }
本文网址:https://www.zhankr.net/141241.html