题解 | 取数游戏

#include <bits/stdc++.h>

using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
typedef long long LL;

const int N=1010;
int n;
int a[N], b[N];
int dp[N][N];   //dp[i, j]表示左边选了i个数，右边选了j个数

int main()
{
    IOS
    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=0; i<=n; i++)
        for(int j=0; j<=n; j++){
            if(i==0 && j==0) continue;
            else if(i==0 && j) dp[i][j]=dp[i][j-1]+a[n-j+1]*b[i+j];
            else if(i && j==0) dp[i][j]=dp[i-1][j]+a[i]*b[i+j];
            else dp[i][j]=max(dp[i][j-1]+a[n-j+1]*b[i+j], dp[i-1][j]+a[i]*b[i+j]);
        }
    int ans=0;
    for(int i=1; i<=n; i++) ans=max(ans, dp[i][n-i]);
    cout<<ans;
    return 0;
}

dp[i, j]表示左边选了i个数，右边选了j个数

当i，j均为0时无前驱状态，跳过。某一个不为0时转移唯一。其他情况就是两种转移路径。

最后遍历找最大值输出即可

#牛客春招刷题训练营#