Guest User

Untitled

a guest
Jul 29th, 2012
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <stack>
  7. #include <queue>
  8. #include <algorithm>
  9. #include <sstream>
  10. #include <iostream>
  11. #include <iomanip>
  12. #include <cstdio>
  13. #include <cmath>
  14. #include <cstdlib>
  15. #include <ctime>
  16. #include <memory.h>
  17.  
  18. using namespace std;
  19.  
  20. #define ABS(a) ((a>0)?a:-(a))
  21. #define MIN(a,b) ((a<b)?(a):(b))
  22. #define MAX(a,b) ((a<b)?(b):(a))
  23. #define FOR(i,a,n) for (int i=(a);i<(n);++i)
  24. #define FI(i,n) for (int i=0; i<(n); ++i)
  25. #define pnt pair <int, int>
  26. #define mp make_pair
  27. #define PI 3.14159265358979
  28. #define MEMS(a,b) memset(a,b,sizeof(a))
  29. #define LL long long
  30. #define U unsigned
  31.  
  32. int n,m;
  33. int dp[1010][1010][3];
  34. int a[1010][1010];
  35. int was[1010][1010][3];
  36. int way[1010][1010][3];
  37. int t;
  38. int r(int x, int y, int from)
  39. {
  40.     if ((x==n-1) && (y==m-1))
  41.         return a[x][y];
  42.     if (was[x][y][from]==t)
  43.         return dp[x][y][from];
  44.     was[x][y][from]=t;
  45.     int res=-1000000000;
  46.     if (x<n-1)
  47.         res=max(res,a[x][y]+r(x+1,y,0));
  48.     if ((y<m-1) && (from!=2))
  49.         res=max(res,a[x][y]+r(x,y+1,1));
  50.     if ((y>0) && (from!=1))
  51.         res=max(res,a[x][y]+r(x,y-1,2));
  52.     return dp[x][y][from]=res;
  53. }
  54. int main()
  55. {
  56. #ifdef Fcdkbear
  57.     freopen("in.txt","r",stdin);
  58. #endif
  59.     t=0;
  60.     while (1)
  61.     {
  62.         t++;
  63.         scanf("%d%d",&n,&m);
  64.         if ((n==0) && (m==0))
  65.             break;
  66.         //MEMS(was,0);
  67.         FOR(i,0,n)
  68.             FOR(j,0,m)
  69.                 scanf("%d",&a[i][j]);
  70.         int res=r(0,0,0);
  71.         printf("Teste %d\n",t);
  72.         cout<<res<<endl<<endl;
  73.     }
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment