Posted on 2011-12-01 15:38
C小加 閱讀(1311)
評論(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;
}