取数游戏2（区间DP）

本文主要是介绍取数游戏2（区间DP），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int a[N], b[N], dp[N][N];
int main(){
    int t;
    cin >> t;
    while(t --){
        int n;
        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 = 1; i <= n; i ++)
            dp[i][i] = a[i] * b[n];
        for(int i = n; i >= 1; i --){
            for(int j = i + 1; j <= n; j ++){
                dp[i][j] = max(dp[i+1][j]+a[i]*b[n-(j-i)],dp[i][j-1]+a[j]*b[n-(j-i)]);
            }
        }
        cout << dp[1][n] << endl;
    }
    
    
    return 0;
}

这篇关于取数游戏2（区间DP）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！