Advertisement
FHVirus

Untitled

Oct 29th, 2020
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4.  
  5. const int N = 105;
  6.  
  7. int m, n, g[N][N], dp[N*2][N][N];
  8.  
  9. inline bool good(int i, int j){
  10.     return j >= 0 and i - j >= 0 and j < m and i - j < n and g[j][i - j] != -1;
  11. }
  12.  
  13. int main(){
  14.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  15.     cin >> m >> n;
  16.     for(int i = 0; i < m; ++i){
  17.         for(int j = 0; j < n; ++j){
  18.             cin >> g[i][j];
  19.         }
  20.     }
  21.     // from (0, 0) to (m-1, n-1)
  22.     for(int i = 0; i <= m + n - 2; ++i){
  23.         for(int j = 0; j <= i; ++j){
  24.             if(!good(i, j)) continue;
  25.             for(int k = 0; k <= i; ++k){
  26.                 if(!good(i, k)) continue;
  27.                 dp[i][j][k] = g[j][i - j] + (j != k ? g[k][i - k] : 0);
  28.  
  29.                 int mx = 0;
  30.                 if(good(i-1, j) and good(i-1, k))
  31.                     mx = max(mx, dp[i-1][j][k]);
  32.                 if(good(i-1, j) and good(i-1, k-1))
  33.                     mx = max(mx, dp[i-1][j][k-1]);
  34.                 if(good(i-1, j-1) and good(i-1, k))
  35.                     mx = max(mx, dp[i-1][j-1][k]);
  36.                 if(good(i-1, j-1) and good(i-1, k-1))
  37.                     mx = max(mx, dp[i-1][j-1][k-1]);
  38.                 dp[i][j][k] += mx;
  39.             }
  40.         }
  41.     }
  42.     cout << dp[m + n - 2][m-1][m-1];
  43.     return 0;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement