Paste Search Dynamic
Recent pastes
ans max
  1. #include <bits/stdc++.h>
  2. #define FOR(i,a,b) for(int i= a ; i <= b ; i++)
  3. using namespace std;
  4. const int N = 2305;
  5. const long long oo = 1e18 + 7;
  6. int m, n, k;
  7. long long Val[N][N], f[N][N][11];
  8. // f[i][j][t] dang dung o o(i,j) va da dung t lan di chuyen dac biet
  9. int main()
  10. {
  11.     //ios_base:: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  12.     //freopen("garden.inp","r",stdin);
  13.     //freopen("garden.out","w",stdout);
  14.     cin >> m >> n >> k;
  15.     memset(f, -0x3f, sizeof f);
  16.     for(i,1,m)for(j,1,n) cin >> Val[i][j];
  17.     ///xuat phat tu 1 o bat ki cua cot dau tien
  18.     for(i,1,m)f[i][1][0] = Val[i][1];
  19.     /// quy hoach dong: thu tu la t tang dan, sau do den j,xong den i
  20.     for(t,0,k)for(j,1,n)
  21.     for(i,1,m)
  22.     if(f[i][j][t] > -oo){
  23.        /// su dung phep di chuyen binh thuong tu (i,j) den (i-1,j+1),(i,j+1),(i+1,j+1)
  24.        if(j < n)
  25.        for(z,i-1,i+1) if(z >= 1 && z <= m)
  26.         f[z][j+1][t] = max(f[z][j+1][t],f[i][j][t] + Val[z][j+1]);
  27.        ///su dung phep di chuyen dac biet
  28.        if(t < k){
  29.        for(r,1,m)if(r != i) f[r][j][t+1] = max(f[r][j][t+1], f[i][j][t] + Val[r][j]);
  30.        for(c,1,n)if(c != j) f[i][c][t+1] = max(f[i][c][t+1], f[i][j][t] + Val[i][c]);
  31.       }
  32.     }
  33.     ///ket qua o cot cuoi cung, hang bat ki, so luong lan su dung phep di chuyen dac biet tuy y
  34.     long long ans = -oo;
  35.     for(i,1,m)for(t,0,k) ans = max(ans,f[i][n][t]);
  36.     cout << ans;
  37.     return 0;
  38. }
  39. /** vandeeptry **/
  40.  
Parsed in 0.005 seconds