很简单的水DP，一个斜数塔。
状态转移公式是：map[x][y]=Max(map[x-1][y]+map[x][y],map[x][y-1]+map[x][y]);题目中说一个点可以直接到它斜下角的点，但是计算的时候这种情况完全不用考虑。所以点的值都是非负的。既然可以走两步的路，为什么要走一步？！多走一步路就多捡一个格子的金子。
第一次提交的时候忘了每一个测试实例后面要跟一个空白行，PE了一次。
[cpp] #include
#include
#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
else
j++;
}
printf("Scenario #%d:\n",count++);
printf("%d\n",map[n][m]);
printf("\n");
}
return 0;
}
#include
#include
#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
else
j++;
}
printf("Scenario #%d:\n",count++);
printf("%d\n",map[n][m]);
printf("\n");
}
return 0;
}