Advertisement
AlexAvram

Untitled

Apr 8th, 2025
18
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.27 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 ale;
  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