fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = 4e18;
  5. const int MAXM = 2005;
  6.  
  7. // Khai báo biến toàn cục (cấp phát bộ nhớ tĩnh 1 lần duy nhất)
  8. long long dp_max[MAXM];
  9. long long dp_min[MAXM];
  10. long long cur_max[MAXM];
  11. long long cur_min[MAXM];
  12.  
  13. int main() {
  14.     ios_base::sync_with_stdio(false);
  15.     cin.tie(NULL);
  16.  
  17.     int n, m;
  18.     cin >> n >> m;
  19.  
  20.     // Khởi tạo trạng thái ban đầu cho hàng 0 / trước hàng 1
  21.     fill(dp_max + 1, dp_max + m + 1, -INF);
  22.     fill(dp_min + 1, dp_min + m + 1, INF);
  23.  
  24.     for (int i = 1; i <= n; ++i) {
  25.         // Tái sử dụng mảng toàn cục bằng cách reset giá trị ban đầu cho hàng i
  26.         fill(cur_max + 1, cur_max + m + 1, -INF);
  27.         fill(cur_min + 1, cur_min + m + 1, INF);
  28.  
  29.         for (int j = 1; j <= m; ++j) {
  30.             long long val;
  31.             cin >> val;
  32.  
  33.             if (i == 1 && j == 1) {
  34.                 cur_max[1] = val;
  35.                 cur_min[1] = val;
  36.                 continue;
  37.             }
  38.  
  39.             // Hướng di chuyển XUỐNG DƯỚI (từ ô (i-1, j))
  40.             if (i > 1) {
  41.                 cur_max[j] = max(cur_max[j], dp_max[j] + val);
  42.                 cur_min[j] = min(cur_min[j], dp_min[j] + val);
  43.             }
  44.  
  45.             // Hướng di chuyển SANG PHẢI (từ ô (i, j-1))
  46.             if (j > 1) {
  47.                 cur_max[j] = max(cur_max[j], -cur_min[j - 1] + val);
  48.                 cur_min[j] = min(cur_min[j], -cur_max[j - 1] + val);
  49.             }
  50.         }
  51.  
  52.         // Rolling: Copy kết quả hàng hiện tại (cur) sang hàng cũ (dp) để chuẩn bị cho hàng tiếp theo
  53.         for (int j = 1; j <= m; ++j) {
  54.             dp_max[j] = cur_max[j];
  55.             dp_min[j] = cur_min[j];
  56.         }
  57.     }
  58.  
  59.     cout << dp_max[m] << "\n";
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
2 2
-5 10
-20 5
stdout
copy 
30
https://ideone.com/vGcD9l
demo dp tối ưu bộ nhớ rolling array
language:
C++14 (gcc 8.3)
created:
7 hours 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!