取数游戏2 题解

dp[j][k]用于表示j到k的闭区间，然后逆向扩展区间，从最后一次取数一直扩展到第一次取数。
第一次取数的位置一定为最左或最右，即dp[1][n]=max(dp[2][n]+取数,dp[1][n-1]+取数）。
问题得到解决。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1050][1050];
ll a[1050];
ll b[1050];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&b[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;i+j-1<=n;j++)
            {
                int k=i+j-1;
                dp[j][k]=max(dp[j][k],max(dp[j][k-1]+a[k]*b[n-i+1],dp[j+1][k]+a[j]*b[n-i+1]));
            }
        }
        printf("%lld\n",dp[1][n]);
    }
}