取数游戏2

比较直接的dp，状态当前选择左端还是右端，以及i之前选了几个左端
dp[ i ][ j ][ 0/1 ], 表示当前选择右端，1表示当前选择左端，j表示到达i时，已经选择j个左端。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1100;
int a[maxn],b[maxn],dp[maxn][maxn][2];//到达第i个点，选了j个左端点
int main()
{
    int n,t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j>0) dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j-1][0],dp[i-1][j-1][1])+a[j]*b[i]);
                dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j][0],dp[i-1][j][1])+a[n-i+j+1]*b[i]);
            }
        }
        int ans=0;
        for(int i=0;i<=n;i++)
        {
           ans=max(ans,max(dp[n][i][0],dp[n][i][1]));
        }
        cout<<ans<<endl;
    }
}