以下是我的代碼：
#include<stdio.h>
#define maxn 107
#define INF 20000000
long m,n,ans,pos,a[maxn][maxn],d[maxn][maxn],f[maxn][maxn];
int main()
{
while(scanf("%ld%ld",&m,&n)==2)
{
for(long i=1;i<=m;i++)
for(long j=1;j<=n;j++)
scanf("%ld",&a[i][j]);
for(long i=0;i<=m+1;i++)
for(long j=0;j<=n+1;j++)
{
d[i][j]=INF;
f[i][j]=-1;
}
for(long i=0;i<=m+1;i++)
d[i][n+1]=0;
for(long i=n;i>=1;i--)
for(long j=1;j<=m;j++)
if(j==1)
{
if(d[1][i]>d[1][i+1])
{d[1][i]=d[1][i+1];f[1][i]=1;}
if(d[1][i]>d[2][i+1])
{d[1][i]=d[2][i+1];f[1][i]=2;}
if(d[1][i]>d[m][i+1])
{d[1][i]=d[m][i+1];f[1][i]=m;}
d[1][i]+=a[1][i];
}
else if(j==m)
{
if(d[j][i]>d[1][i+1])
{d[j][i]=d[1][i+1];f[j][i]=1;}
if(d[j][i]>d[j-1][i+1])
{d[j][i]=d[j-1][i+1];f[j][i]=j-1;}
if(d[j][i]>d[j][i+1])
{d[j][i]=d[j][i+1];f[j][i]=j;}
d[j][i]+=a[j][i];
}
else
{
if(d[j][i]>d[j-1][i+1])
{d[j][i]=d[j-1][i+1];f[j][i]=j-1;}
if(d[j][i]>d[j][i+1])
{d[j][i]=d[j][i+1];f[j][i]=j;}
if(d[j][i]>d[j+1][i+1])
{d[j][i]=d[j+1][i+1];f[j][i]=j+1;}
d[j][i]+=a[j][i];
}
ans=INF;
for(long i=1;i<=m;i++)
if(d[i][1]<ans)
{
ans=d[i][1];
pos=i;
}
bool first=true;
for(long i=1;i<=n;i++)
{
if(first) first=false;
else printf(" ");
printf("%ld",pos);
pos=f[pos][i];
}putchar('\n');
printf("%ld\n",ans);
}
return 0;
}
posted on 2010-03-01 21:30
lee1r 閱讀(759)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態(tài)規(guī)劃