题解 | #取数游戏2#

题目描述:
给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。
思路与分析：
我们定义它在区间[l,r]之间的最大值为dp[l][r]。
而dp[l][r]的值是由max(dfs(l+1,r,i+1)+b[i]a[l],dfs(l,r-1,i+1)+b[i]a[r])得来的。
所以我们可以的到dfs的代码

int dfs(int l,int r,int i)
{
    if(i==n+1)return 0;
    if(dp[l][r]!=0)return dp[l][r];
    return dp[l][r]=max(dfs(l+1,r,i+1)+b[i]*a[l],dfs(l,r-1,i+1)+b[i]*a[r]);
}

由此代码我们便可推得它的递推式

dp[j][j+i]=max(dp[j+1][j+i]+a[j]*b[n-i],dp[j][j+i-1]+a[j+i]*b[n-i]);

AC代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e3+10;
ll a[N],b[N],dp[N][N];        
int n;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(dp,0,sizeof(dp));
        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];
        for(int i=1;i<n;i++)
            for(int j=1;j+i<=n;j++)
                dp[j][j+i]=max(dp[j+1][j+i]+a[j]*b[n-i],dp[j][j+i-1]+a[j+i]*b[n-i]);
        cout<<dp[1][n]<<'\n';
    }
    return 0;
}

另外此题也能用记忆化搜索做

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e3+10;
ll a[N],b[N],dp[N][N];        
int n;
int dfs(int,int,int);
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        cout<<dfs(1,n,1)<<'\n';
    }
    return 0;
}
int dfs(int l,int r,int i)
{
    if(i==n+1)return 0;
    if(dp[l][r]!=0)return dp[l][r];
    return dp[l][r]=max(dfs(l+1,r,i+1)+b[i]*a[l],dfs(l,r-1,i+1)+b[i]*a[r]);
}