NC14701 取数游戏2

dp[i][j]表示左边去了i个数，右边取j个数时所获得最大值

#include <iostream>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int num;
        cin >> num;
        int nums1[maxn];
        int nums2[maxn];
        for (int i = 1; i <= num; i++) {
            cin >> nums1[i];
        }
        for (int j = 1; j <= num; j++) {
            cin >> nums2[j];
        }
        for (int i = 0; i <maxn; i++) {
            for (int j = 0; j <maxn; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 1; i <= num; i++) {
            dp[i][0] =dp[i-1][0]+ nums1[i] * nums2[i];
            dp[0][i] = dp[0][i - 1] + nums1[num-i+1] * nums2[i];
        }
        int ans = 0;
        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= num; j++) {
                dp[i][j] = max(dp[i - 1][j] + nums1[i] * nums2[i + j], dp[i][j - 1] + nums1[num - j + 1] * nums2[i + j]);
                if (i + j == num)ans = max(ans, dp[i][j]);
            }
        }
        cout << ans<<endl;
    }
}