NC14701. 取数游戏2
描述
输入描述
第一行一个数T，表示有T组数据。
对于每组数据，第一行一个整数n，
接下来两行分别给出A数列与B数列。
输出描述
每一组数据输出一行，最大的∑vi。
示例1
输入:
2 2 1 1000 2 1 5 1 3 5 2 4 1 2 3 4 5
输出:
2001 52
说明:
对于第二个样例，C++(clang++ 11.0.1) 解法, 执行用时: 15ms, 内存消耗: 384K, 提交时间: 2022-12-30 18:10:09
#include<bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
while (T--) {
int n; cin >> n;
vector<int> A(n); for (auto &x: A) cin >> x;
vector<int> B(n); for (auto &x: B) cin >> x;
vector<int> cur(n);
for (int l = 1; l <= n; l++) {
for (int i = 0; i + l <= n; i++) cur[i] = max(cur[i]+A[i+l-1]*B[n-l], A[i]*B[n-l]+cur[i+1]);
}
cout << cur[0] << endl;
}
}