想让部长批阅签署一份文件。但只有当部长的下属部门核准后，部长才签署一份文件。部门是一座M层的建筑物，从地面开始数起为1到M层。1<=M<=100.每一层有N个房间(1<=N<=500),也是从1到N编号。每一个房间里有且只有一个官员。
一份文件要被部门签署，必须有至少一位（M层建筑物里的）官员签署；一个官员必须至少满足以下一项条件才能签署一个文件：
条件a：该官员在第一层工作。
条件b：该文件已经被楼下同一间房的官员签署。
条件c：该文件已经被隔壁的官员签署（所谓隔壁，是指同一层，且房间号相差为1。
每一个官员签署一份文件，收取一点费用，这个费用为不超过10^9的正整数。
请找出签署一份文件要付出的最少费用。
input：
首行为2个整数，空格隔开。第一个数为M，表示M层；第二数为N，表示每层N个房间。 以下M行，每行N个整数，空格隔开，描述每间房子的官员签署一份文件收取的费用（第l行的第k个整数表示第l层的第k间房的费用。
output：
求出让文件顺利签署所经过的房间号，按顺序一行一个，这必须是付款最少的路线。 假如有多个方案，输出任一个即可。
input：
3 4
10 10 1 10
2 2 2 10
1 10 10 10
output：
3
3
2
1
1
【参考程序】：
#include<iostream>
using namespace std;
struct node
{
int x,y;
} pre[101][501];
long long f[101][501],fee[101][501];
int ans[50010];
long n,m,t;
int main()
{
scanf("%ld%ld",&m,&n);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
scanf("%lld",&fee[i][j]);
memset(f,0,sizeof(f));memset(pre,0,sizeof(pre));
for (int i=1;i<=n;i++) f[1][i]=fee[1][i];
for (int i=2;i<=m;i++)
{
for (int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]+fee[i][j];
pre[i][j].x=i-1;pre[i][j].y=j;
}
for (int j=2;j<=n;j++)
{
t=f[i][j-1]+fee[i][j];
if (f[i][j]>t)
{
f[i][j]=t;
pre[i][j].x=i;pre[i][j].y=j-1;
}
}
for (int j=n-1;j>=1;j--)
{
t=f[i][j+1]+fee[i][j];
if (f[i][j]>t)
{
f[i][j]=t;
pre[i][j].x=i;pre[i][j].y=j+1;
}
}
}
t=0x7FFFFFFF;
int i,j;
for (j=1;j<=n;j++)
if (t>f[m][j])
{
t=f[m][j];
i=j;
}
j=i;i=m;n=0;
while (i>0)
{
n++;ans[n]=j;
t=pre[i][j].x;
j=pre[i][j].y;
i=t;
}
for (i=n;i>=1;i--) printf("%d\n",ans[i]);
return 0;
}
【参考程序】：
#include<iostream>
using namespace std;
long long MIN[501],sum[501];
long long fee[501],old[501];
int pre[101][501];
int n,m;
void printf_path(int f,int p)
{
if (f==1)
{
printf("%d\n",p);
return ;
}
printf_path(f-1,pre[f][p]);
if (pre[f][p]<p)
for (int i=pre[f][p];i<=p;i++)
printf("%d\n",i);
else
for (int i=pre[f][p];i>=p;i--)
printf("%d\n",i);
}
int main()
{
scanf("%d%d",&m,&n);
for (int i=1;i<=n;i++)
scanf("%lld",&MIN[i]);
for (int k=2;k<=m;k++)
{
memcpy(old,MIN,sizeof(long long)*501);
for (int i=1;i<=n;i++)
{
scanf("%lld",&fee[i]);
MIN[i]=0x7FFFFFFF;
sum[i]=0;
}
sum[1]=fee[1];
for (int i=2;i<=n;i++)
sum[i]+=sum[i-1]+fee[i];
for (int i=1;i<=n;i++)
{
for (int j=i;j<=n;j++)
{
if (old[j]+sum[j]<MIN[i])
{
MIN[i]=old[j]+sum[j];
pre[k][i]=j;
}
if (old[i]+sum[j]<MIN[j])
{
MIN[j]=old[i]+sum[j];
pre[k][j]=i;
}
}
for (int j=i+1;j<=n;j++)
sum[j]-=fee[i];
}
}
long long s=0x7FFFFFFF;
int tail;
for (int i=1;i<=n;i++)
if (MIN[i]<s)
{
s=MIN[i];
tail=i;
}
printf_path(m,tail);
return 0;
}