fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define N 1005
  4.  
  5. int n, m, ans = INT_MIN;
  6. int A[N], B[N], dp[N][N];
  7.  
  8. void calculate() {
  9.     memset(dp, 0, sizeof(dp)); // 初始化 DP 陣列
  10.  
  11.     // DP 計算兩個區間的總和
  12.     for (int i = 1; i <= n; i++) {
  13.         for (int j = 1; j <= m; j++) {
  14.             // 初始情況：取這一對的總和
  15.             dp[i][j] = A[i] + B[j];
  16.             if (i > 1 && j > 1) {
  17.                 // 考慮延續前一個 DP 結果，更新最大總和
  18.                 dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + A[i] + B[j]);
  19.             }
  20.             ans = max(ans, dp[i][j]);
  21.         }
  22.     }
  23. }
  24.  
  25. int main() {
  26.     // 輸入陣列長度與數值
  27.     scanf("%d%d", &n, &m);
  28.     for (int i = 1; i <= n; i++) {
  29.         scanf("%d", A + i);
  30.     }
  31.     for (int i = 1; i <= m; i++) {
  32.         scanf("%d", B + i);
  33.     }
  34.  
  35.     // 計算不翻轉的情況
  36.     calculate();
  37.  
  38.     // 翻轉 A 陣列並再次計算
  39.     for (int i = 1; i <= n / 2; i++) {
  40.         swap(A[i], A[n + 1 - i]);
  41.     }
  42.     calculate();
  43.  
  44.     // 輸出最大總和
  45.     printf("%d\n", ans);
  46. }
  47.  
Success #stdin #stdout 0.01s 7608KB
comments (?)
stdin 
5 5
-3 -3 3 3 -3
2 2 2 2 2
stdout 
10
https://ideone.com/p3fvzs
language:
C++14 (gcc 8.3)
created:
17 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!