Advertisement
AlexAvram

Untitled

Apr 8th, 2025
310
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. //birocratie2 #4611
  2. #include <iostream>
  3. #include <fstream>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7. string fisier="birocratie";
  8. ifstream fin(fisier+".in");
  9. ofstream fout(fisier+".out");
  10.  
  11. #define MINIM -1e9
  12. #define Nmax 1001
  13.  
  14. int n, mat[Nmax][Nmax];
  15. int dp[Nmax][Nmax];
  16. /*
  17. programare dinamica pe diagonale;
  18. //
  19. parcurgem pe rand toate diagonalele paralele cu cea secundara,
  20. de sus in jos iar apoi de jos in sus; parcurgea in ambele directii
  21. este pentru a verifica ca toate costurile sunt calculate optim,
  22. fara sa conteze ordinea in care procesam elemente;
  23. in cazul fiecarui element, vedem daca putem ajunge la el
  24. prin una dintre celelalte 2 variante posibile de deplasare
  25. (in jos sau la dreapta);
  26. daca exista, alegem calea de castig maxim si o adunam elementului
  27. curent;
  28. */
  29. void citire()
  30. {
  31.     fin>>n;
  32.     for (int i=1; i<=n; ++i)
  33.         for (int j=1; j<=n; ++j)
  34.             fin>>mat[i][j];
  35. }
  36. bool sunt_in_matrice(int i, int j)
  37. {
  38.     return i>=1 && i<=n && j>=1 && j<=n;
  39. }
  40. void rezolvare()
  41. {
  42.     dp[1][1]=mat[1][1];
  43.     for(int diag=2; diag<=2*n-1; ++diag)
  44.     {
  45.         int suma=MINIM;
  46.         for(int i=1; i<=n; ++i)
  47.         {
  48.             int j=diag-i+1;
  49.             if(sunt_in_matrice(i,j))
  50.             {
  51.                 if(sunt_in_matrice(i-1,j))
  52.                 {
  53.                     suma=max(suma,dp[i-1][j]);
  54.                 }
  55.                 if(sunt_in_matrice(i,j-1))
  56.                 {
  57.                     suma=max(suma,dp[i][j-1]);
  58.                 }
  59.                 dp[i][j]=suma+mat[i][j];
  60.                 suma+=mat[i][j];
  61.             }
  62.         }
  63.         suma=MINIM;
  64.         for(int i=n; i>=1; --i)
  65.         {
  66.             int j=diag-i+1;
  67.             if(sunt_in_matrice(i,j))
  68.             {
  69.                 if(sunt_in_matrice(i-1,j))
  70.                 {
  71.                     suma=max(suma,dp[i-1][j]);
  72.                 }
  73.                 if(sunt_in_matrice(i,j-1))
  74.                 {
  75.                     suma=max(suma,dp[i][j-1]);
  76.                 }
  77.                 dp[i][j]=max(dp[i][j],suma+mat[i][j]);
  78.                 //vedem daca obtinem o imbunatatire fata
  79.                 //de prima parcurgere
  80.                 suma+=mat[i][j];
  81.             }
  82.         }
  83.     }
  84.     fout<<dp[n][n];
  85. }
  86. int main()
  87. {
  88.     citire();
  89.     rezolvare();
  90.     return 0;
  91. }
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement