题解 | #取数游戏#

解题思路：

• 这题应该是前面DP49的简化版，不需要高精度，令$d{p}_{l,r}dp\_\{l,r\}$表示左侧取$ll$个，右侧取$rr$个的最大值，那么可以得到状态转移方程：$d{p}_{l,r}=\max (d{p}_{l-1,r}+a_l\times b_i,d{p}_{l,r-1}+a_{n-r+1}\times b_i)dp\_\{l,r\}\; =\; \backslash max(dp\_\{l-1,r\}\; +\; a\_l\; \backslash times\; b\_i,\; dp\_\{l,r-1\}\; +\; a\_\{n-r+1\}\; \backslash times\; b\_i)$。

#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;
}