Advertisement
Saleh127

SPOJ MISERMAN / DP

Nov 7th, 2021
697
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. #define get_lost_idiot return 0
  6. #define nl '\n'
  7.  
  8. ll a[1005][1005];
  9. ll dp[200][200];
  10. ll n,m;
  11.  
  12.  
  13. int main()
  14. {
  15.     ios_base::sync_with_stdio(0);
  16.     cin.tie(0);
  17.     cout.tie(0);
  18.  
  19.     ll i,j,k,l,h,ans=1000000000000000;
  20.  
  21.     cin>>n>>m;
  22.  
  23.  
  24.     for(i=0; i<n; i++)
  25.     {
  26.         for(j=0; j<m; j++)
  27.         {
  28.             cin>>a[i][j];
  29.         }
  30.     }
  31.  
  32.     for(i=1; i<n; i++)
  33.     {
  34.         for(j=0; j<m; j++)
  35.         {
  36.             k=a[i-1][j];
  37.  
  38.             if(j>0) k=min(k,a[i-1][j-1]);
  39.  
  40.             if(j+1<m) k=min(k,a[i-1][j+1]);
  41.  
  42.             a[i][j]+=k;
  43.         }
  44.  
  45.     }
  46.  
  47.     for(j=0; j<m; j++)
  48.     {
  49.         ans=min(ans,a[n-1][j]);
  50.     }
  51.  
  52.  
  53.     cout<<ans<<nl;
  54.  
  55.  
  56.     get_lost_idiot;
  57. }
  58.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement