hdu 2391（水DP）

很簡單的水DP，一個斜數塔。

狀態轉移公式是：map[x][y]=Max(map[x-1][y]+map[x][y],map[x][y-1]+map[x][y]);題目中說一個點可以直接到它斜下角的點，但是計算的時候這種情況完全不用考慮。所以點的值都是非負的。既然可以走兩步的路，為什麼要走一步？！多走一步路就多撿一個格子的金子。

第一次提交的時候忘了每一個測試實例後面要跟一個空白行，PE了一次。

[cpp] #include<stdio.h>  
#include<string.h>  
#define N 1005  
int map[N][N]; 
int Max(int x,int y) 
{ 
    return x>y?x:y; 
} 
int main() 
{ 
    int T; 
    int m,n; 
    int i,j; 
    scanf("%d",&T); 
    int count=1; 
    while(T--) 
    { 
        scanf("%d%d",&n,&m); 
        for(i=0;i<=n+1;i++) 
        { 
            for(j=0;j<=m+1;j++) 
                map[i][j]=0; 
        } 
        for(i=1;i<=n;i++) 
        { 
            for(j=1;j<=m;j++) 
                scanf("%d",&map[i][j]); 
        } 
        i=1,j=1; 
        int x,y; 
        while(i<=n&&j<=m) 
        { 
            x=i,y=j; 
            while(x>=1&&y<=m) 
            { 
                map[x][y]=Max(map[x-1][y]+map[x][y],map[x][y-1]+map[x][y]); 
                x--; 
                y++; 
            } 
            if(i<n) 
                i++; 
            else 
                j++; 
        } 
        printf("Scenario #%d:\n",count++); 
        printf("%d\n",map[n][m]); 
        printf("\n"); 
    } 
    return 0; 
} 

#include<stdio.h>
#include<string.h>
#define N 1005
int map[N][N];
int Max(int x,int y)
{
 return x>y?x:y;
}
int main()
{
 int T;
 int m,n;
 int i,j;
 scanf("%d",&T);
 int count=1;
 while(T--)
 {
  scanf("%d%d",&n,&m);
  for(i=0;i<=n+1;i++)
  {
   for(j=0;j<=m+1;j++)
    map[i][j]=0;
  }
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=m;j++)
    scanf("%d",&map[i][j]);
  }
  i=1,j=1;
  int x,y;
  while(i<=n&&j<=m)
  {
   x=i,y=j;
   while(x>=1&&y<=m)
   {
    map[x][y]=Max(map[x-1][y]+map[x][y],map[x][y-1]+map[x][y]);
    x--;
    y++;
   }
   if(i<n)
    i++;
   else
    j++;
  }
  printf("Scenario #%d:\n",count++);
  printf("%d\n",map[n][m]);
  printf("\n");
 }
 return 0;
}