取数游戏2

题目描述

给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。

输入描述:

第一行一个数T，表示有T组数据。
对于每组数据，第一行一个整数n，
接下来两行分别给出A数列与B数列。

输出描述:

每一组数据输出一行，最大的∑vi。

题解

这道题还是很好想的，我们每次做的决策就是是选最左端的还是选择最右端的。我们可以设置dp[i][j]表示剩下的区间是从i到j的，也就是我们选了1~i-1和j+1到n。那么很明显，dp[i][j]=max(dp[i-1][j]+a[i]b[k],dp[i][j+1]+a[j]b[k])。在枚举的时候我们可以直接枚举前面选几个来算出后面的位置。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1050],b[1050];
long long dp[1050][1050];
int main(){
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        for(int i=1;i<=n;++i)cin>>b[i];
        long long ans=0;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=i;++j){
                if(!j)dp[j][n-i+j+1]=dp[j][n-i+j+2]+a[n-i+j+1]*b[i];
                else if(i==j)dp[j][n-i+j+1]=dp[j-1][n-i+j+1]+a[j]*b[i];
                else dp[j][n-i+j+1]=max(dp[j][n-i+j+2]+a[n-i+j+1]*b[i],dp[j-1][n-i+j+1]+a[j]*b[i]);
                ans=max(ans,dp[j][n-i+j+1]);
                //cout<<j<<" "<<n-i+j+1<<" "<<dp[j][n-i+j+1]<<endl;
            }
        }
        cout<<ans<<endl;
    }
}