简单的动态规划，对于每一层，先把每个点赋值为其下层的值，然后从左向右动归一次，再从右向左动归一次，同时如果更新了最小值，记录路径。
有个问题就是里层动归的方向，我开始是先从左到右，再从右到左，结果第15组output limit exceed 方向一换又AC了，怀疑评测系统有问题。
#include<stdio.h>
long m,n,i,j,jl;
long ans;
long v[601][601],f[601][601],p[601][601];
int main()
{
scanf("%ld %ld",&m,&n);
for (i=1;i<=m;i++)
for (j=1;j<=n;j++)
{
scanf("%ld",&v[i][j]);
}
for (i=m;i>=1;i--)
{
for (j=1;j<=n;j++)
{
p[i][j]=j;
f[i][j]=v[i][j]+f[i+1][j];
}
for (j=n-1;j>=1;j--)
if (f[i][j]>f[i][j+1]+v[i][j])
{
f[i][j]=f[i][j+1]+v[i][j];
p[i][j]=j+1;
}
for (j=2;j<=n;j++)
if (f[i][j]>f[i][j-1]+v[i][j])
{
f[i][j]=f[i][j-1]+v[i][j];
p[i][j]=j-1;
}
}
ans=2100000000;
for (i=1;i<=n;i++)
if (ans>f[1][i])
{
ans=f[1][i];
jl=i;
}
i=1;
while (i<=m)
{
printf("%ld\n",jl);
if (jl==p[i][jl])
{
jl=p[i][jl];
i++;
}
else
jl=p[i][jl];
}
}
posted on 2011-07-05 22:59
梦转千寻 阅读(43)
评论(0) 编辑 收藏 引用