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; } }
题解汇总 文章被收录于专栏
无