题解 | #取数游戏2#

取数游戏2 (nowcoder.com)

转移方程：

状态表示：

F(i,j)表示区间i到j取得的最大值。

边界：

目标：

代码：

void solve() {
    int tt; cin>>tt;
    while(tt--) {
        int n; cin>>n;
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        vector<int> a(n + 1), b(a);
        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) f[i][i] = a[i] * b[n];
        for(int len = 2; len <= n; ++len) {
            for(int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;
                f[i][j] = max(f[i][j], f[i+1][j] + a[i] * b[n - len + 1]);
                f[i][j] = max(f[i][j], f[i][j-1] + a[j] * b[n - len + 1]);
            }
        }
        cout<<f[1][n]<<endl;
    }
}

// 将b翻转
void solve() {
    int tt; cin>>tt;
    while(tt--) {
        int n; cin>>n;
        vector<vector<int>> f(n + 1, vector<int>(n + 1));
        vector<int> a(n + 1), b(a);
        for(int i = 1; i <= n; ++i) cin>>a[i];
        for(int i = 1; i <= n; ++i) cin>>b[i];
        reverse(b.begin()+1, b.end());
        // swap(b[0], b[n]);
        // cout<<b[1]<<endl;
        for(int i = 1; i <= n; ++i) f[i][i] = a[i] * b[1];
        for(int len = 2; len <= n; ++len) {
            for(int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;
                f[i][j] = max(f[i][j], f[i+1][j] + a[i] * b[j - i + 1]);
                f[i][j] = max(f[i][j], f[i][j-1] + a[j] * b[j - i + 1]);
                // cout<<f[i][j]<<" ";
            }
            // puts("");
        }
        cout<<f[1][n]<<endl;
    }
}