Advertisement
jeff69

Untitled

Apr 14th, 2016
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.02 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <fstream>
  5. #include <cstring>
  6. #include <string>
  7. #include <functional>
  8. #include <cmath>
  9. #include<algorithm>
  10. typedef long long ll;
  11. using namespace std;
  12. int a[1000][1000], n;
  13. ll dp[1002][1002];
  14. ll solve(int x, int y){
  15. if (x >= n || y >= n){
  16. return 0;
  17. }
  18. ll ret = 0;
  19. if (dp[x][y] != -1)return dp[x][y];
  20. ret += a[x][y]+max(solve(x + 1, y), solve(x, y + 1));
  21. dp[x][y] = ret;
  22. return ret;
  23.  
  24. }
  25. bool check(int x, int y){
  26. return x < n&&y < n;
  27. }
  28. void outputcord(int x,int y){
  29. if (x == n-1&&y == -1+n)return;
  30. if ( dp[x][y + 1] >= dp[x + 1][y]){
  31. cout << x + 1 << ' ' << y + 2<<'\n';
  32. return outputcord(x, y + 1);
  33. }
  34. else{
  35. cout << x + 2 << ' ' << y + 1<<'\n';
  36. return outputcord(x + 1, y) ;
  37. }
  38. }
  39. int main()
  40. {
  41. cin >> n;
  42. for (int i = 0; i < n;i++)
  43. for (int k = 0; k < n; k++)
  44. cin >> a[i][k];
  45. memset(dp, -1, sizeof dp);
  46. cout << solve(0, 0) << '\n';
  47. cout << 1 << ' ' << 1 << '\n';
  48. outputcord(0,0);
  49.  
  50. //cout << n << ' ' << n << '\n';
  51.  
  52.  
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement