NC14701 取数游戏2

链接：https://ac.nowcoder.com/acm/problem/14701
来源：牛客网

题目描述

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

输入描述:

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

输出描述:

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

思路：

区间 $dp$ ：

$dp[i][j]$ 表示区间 $i-j$ 的最优解

首先考虑2个数时候，3个数时候，4个数时候的递推式容易发现的是

当是三个数的时候

$dp[1][3]=max(dp[2][3]+a[1]*b[1],dp[1][2]+a[3]*b[1])$

进而猜测4个数，然后推之发现：

$dp[i][j]=max(dp[i+1][j]+a[i]*b[x],dp[i][j-1]+a[j]*b[x]),x表示第几个数$

$x=n-(j-i)$

然后根据转移方程判断循环的顺序，次序。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
typedef long long ll;
using namespace std;
const int maxn = 2e5 + 10;

int a[1010],b[1010];
int dp[1010][1010];
int main(){
    int t;cin>>t;
    while(t--){
        mem(dp,0);
        int n;cin>>n;
        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){
            dp[i][i]=a[i]*b[n];
        }
//        dp[i][j]=max(dp[i+1][j]+a[i]*b[n-(j-i+1)],dp[i][j-1]+a[j]*b[n-(j-i+1)]);
        for(int i=n;i>0;--i){
            for(int j=i+1;j<=n;++j){
                dp[i][j]=max(dp[i+1][j]+a[i]*b[n-(j-i)],dp[i][j-1]+a[j]*b[n-(j-i)]);
            }
        }
        cout<<dp[1][n]<<endl;

    }
}