Advertisement
Cosmin3105

Problema pcr sah

Oct 31st, 2019
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. ifstream f("date.in");
  7.  
  8. int n, a[101][101], s[101][101], maxp = 0, poz;
  9.  
  10. void drum(int i, int j)
  11. {
  12.     if(i > 0){
  13.         if(s[i][j] - s[i-1][j-1] == a[i][j]) drum(i-1,j-1);
  14.         else if(s[i][j] - s[i-1][j] == a[i][j]) drum(i-1,j);
  15.         else drum(i-1,j+1);
  16.         cout << i << j << "\n";
  17.     }
  18. }
  19.  
  20. int main()
  21. {
  22.     f >> n;
  23.     for(int i = 1; i <= n; i++)
  24.         for(int j = 1; j <= n; j++)
  25.             f >> a[i][j];
  26.  
  27.     for(int i = 1; i <= n; i++)
  28.         s[1][i] = a[1][i];
  29.  
  30.     for(int i = 2; i <= n; i++)
  31.         for(int j = 1; j <= n; j++)
  32.             if(a[i][j] == 0) s[i][j] = a[i-1][j];
  33.             else if(s[i-1][j-1] >= s[i-1][j+1]) s[i][j] = a[i][j] + s[i-1][j-1];
  34.             else s[i][j] = a[i][j] + s[i-1][j+1];
  35.  
  36.     for(int i = 1; i <= n; i++)
  37.         if(s[n][i] > maxp){
  38.             maxp = s[n][i];
  39.             poz = i;
  40.         }
  41.     drum(n,poz);
  42.  
  43.     return 0;
  44. }
  45. /*
  46. 5
  47. 0 0 0 0 0
  48. 0 1 0 1 0
  49. 0 1 1 1 1
  50. 0 0 0 1 1
  51. 0 1 0 1 1
  52. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement