题目大意:
思路:dp逆推。
由最后一列推到第一列。记录路径(只要记录由下一列转化而来的行)。
#include <bits/stdc++.h>
using namespace std;
int a[105][105];
int dp[105][105];
int Next[105][105];
int main()
{
int n, m;
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++)
{
dp[i][m]=a[i][m];
}
for(int i=m-1;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
dp[j][i]=(1<<31)-1;
int x[3]={j-1, j, j+1};
for(int k=0;k<=2;k++)//对路径的处理
{
if(x[k]==0)
{
x[k]=n;
}
if(x[k]==n+1)
{
x[k]=1;
}
}
sort(x, x+3);
for(int k=0;k<3;k++)
{
if(dp[x[k]][i+1]<dp[j][i])
{
dp[j][i]=dp[x[k]][i+1];
Next[j][i]=x[k];
}
}
dp[j][i]+=a[j][i];
}
}
int ans=(1<<31)-1, p;
for(int i=1;i<=n;i++)
{
if(dp[i][1]<ans)
{
ans=dp[i][1];
p=i;
}
}
printf("%d%c",p,(m==1?'\n':' '));
for(int i=1;i<m;i++)
{
printf("%d%c",Next[p][i],(i==m-1?'\n':' '));
p=Next[p][i];
}
printf("%d\n",ans);
}
return 0;
}