题解 | 取数游戏

• 这题应该是前面DP49的简化版，不需要高精度，令dpl,rdpl,r​表示左侧取ll个，右侧取rr个的最大值，那么可以得到状态转移方程：dpl,r=max⁡(dpl−1,r+al×bi,dpl,r−1+an−r+1×bi)dpl,r​=max(dpl−1,r​+al​×bi​,dpl,r−1​+an−r+1​×bi​)。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> a(n+1),b(n+1);
    for(int i = 1; i <= n; ++i) cin>>a[i];
    for(int i = 1; i <= n; ++i) cin>>b[i];
    vector<vector<int>> dp(n+1, vector<int>(n+1));
    for(int len = 1; len <= n; ++len){
        for(int l = 0; l <= len; ++l){
            int r = len - l;
            if(l > 0) dp[l][r] = dp[l-1][r] + a[l] * b[len];
            if(r > 0) dp[l][r] = max(dp[l][r], dp[l][r-1] + a[n-r + 1] * b[len]);
        }
    }
    int mx = 0;
    for(int l = 0; l <= n; ++l){
        mx = max(mx, dp[l][n-l]);
    }
    cout<<mx<<endl;
    return 0;
}