Posted on 2011-12-01 15:38
C小加 阅读(1284)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
双向DP。楼下：f[i][j]=min(f[i][j],f[i-1][j]+room[i][j]);i为层数，j为房间数，room为本房间的价格
左隔壁：f[i][j]=min(f[i][j],f[i][j-1]+room[i][j]);
右隔壁：f[i][j]=min(f[i][j],f[i][j+1]+room[i][j]);
每一层正反各遍历一次。比较的时候要记录路径。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int INF=0x7fffffff-1;
const int MAXM=103;
const int MAXN=503;
int room[MAXM][MAXN];//每个房间的花费
int f[MAXM][MAXN];//到这个房间的时候的最低消费
stack<int> s;//用来路径
typedef struct
{
int l,k;
}prior;
prior p[MAXM][MAXN];//保存来源房间的路径
int main()
{
//freopen("in.txt","r",stdin);
int m,n;
memset(p,0,sizeof(p));
scanf("%d %d",&m,&n);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&room[i][j]);
f[i][j]=INF;
}
}
for(int i=1;i<=n;i++)//给第一层的赋初值
{
f[1][i]=room[1][i];
}
for(int i=2;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(f[i-1][j]!=INF)
if(f[i][j]>f[i-1][j]+room[i][j])//和楼下的比较
{
f[i][j]=f[i-1][j]+room[i][j];
p[i][j].l=i-1;
p[i][j].k=j;
}
if(j>1&&f[i][j-1]!=INF)
if(f[i][j]>f[i][j-1]+room[i][j])//和左边隔壁比较
{
f[i][j]=f[i][j-1]+room[i][j];
p[i][j].l=i;
p[i][j].k=j-1;
}
}
for(int j=n-1;j>=1;j--)
{
if(f[i][j+1]!=INF)
if(f[i][j]>f[i][j+1]+room[i][j])//和右边隔壁比较
{
f[i][j]=f[i][j+1]+room[i][j];
p[i][j].l=i;
p[i][j].k=j+1;
}
}
}
int tk=1;
for(int i=2;i<=n;i++)//找出顶层中花费最少的房间
{
if(f[m][tk]>f[m][i])
{
tk=i;
}
}
int tl=m;
while(tl&&tk) //把路径压栈
{
s.push(tk);
int t1=p[tl][tk].l;
int t2=p[tl][tk].k;
tl=t1;
tk=t2;
}
printf("%d",s.top());
s.pop();
while(!s.empty()) //输出栈中的路径
{
printf(" %d",s.top());
s.pop();
}
return 0;
}