fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = -1000000000;  // vì ta tìm max
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int M;
  10.     cin >> M;
  11.     int N = 2*M;
  12.     int total = 1 + 3*M*(M+1);
  13.  
  14.     // A và dp kích thước (2M+1)^3
  15.     static int A[205][205][205];
  16.     static int dp[205][205][205];
  17.  
  18.     // Khởi A = 0, dp = -INF
  19.     for(int q=0; q<=N; q++){
  20.       for(int r=0; r<=N; r++){
  21.         for(int s=0; s<=N; s++){
  22.           A[q][r][s] = 0;
  23.           dp[q][r][s] = INF;
  24.     }}}
  25.  
  26.     // Đọc total dòng (q,r,s,val)
  27.     for(int i=0; i<total; i++){
  28.       int q,r,s,v;
  29.       cin >> q >> r >> s >> v;
  30.       int qp = q+M, rp = r+M, sp = s+M;
  31.       A[qp][rp][sp] = v;
  32.     }
  33.  
  34.     // Đọc toạ độ đích
  35.     int qt, rt, st;
  36.     cin >> qt >> rt >> st;
  37.     int qpt = qt + M, rpt = rt + M, spt = st + M;
  38.  
  39.     // Base-case: tại (q,r,s) = (0,-M,+M) → (M,0,2M)
  40.     dp[M][0][2*M] = A[M][0][2*M];
  41.  
  42.     // DP: duyệt hàng r' từ 0 tới 2M
  43.     for(int rp = 0; rp <= N; rp++){
  44.       // trong mỗi hàng duyệt qp từ 0..2M
  45.       for(int qp = 0; qp <= N; qp++){
  46.         int sp = 3*M - qp - rp;
  47.         if(sp < 0 || sp > N) continue;   // nếu (qp,rp,sp) không hợp lệ thì bỏ qua
  48.  
  49.         // đã có giá trị base-case ở hàng rp=0, qp=M; những ô khác dp[..] ban đầu = -INF
  50.         int best = dp[qp][rp][sp];
  51.         // chuyển từ phải → trái ngược lại: (qp-1, rp, sp+1)
  52.         if(qp-1 >= 0 && sp+1 <= N)
  53.           best = max(best, dp[qp-1][rp][sp+1] + A[qp][rp][sp]);
  54.         // chuyển từ dưới trái lên ngược lại: (qp+1, rp-1, sp)
  55.         if(qp+1 <= N && rp-1 >= 0)
  56.           best = max(best, dp[qp+1][rp-1][sp] + A[qp][rp][sp]);
  57.         // chuyển từ dưới phải lên ngược lại: (qp, rp-1, sp+1)
  58.         if(rp-1 >= 0 && sp+1 <= N)
  59.           best = max(best, dp[qp][rp-1][sp+1] + A[qp][rp][sp]);
  60.  
  61.         dp[qp][rp][sp] = best;
  62.       }
  63.     }
  64.  
  65.     // In kết quả tại ô đích (qpt,rpt,spt)
  66.     cout << dp[qpt][rpt][spt] << "\n";
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 5672KB
comments (?)
stdin
copy 
1
0 0 0 5
0 -1 1 5
0 1 -1 5
-1 0 1 5
1 0 -1 5
-1 1 0 5
1 -1 0 5
0 1 -1
stdout
copy 
25
https://ideone.com/hW8XHJ
language:
C++14 (gcc 8.3)
created:
1 day 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!