題目的意思是..第一行走到第M行的最小消費. 可以往下走一步，可以往左走一步,可以往右走一步.
可以從第一行任意個位置出發。只要到達第M行的任意個位置就結束。。
按意思可得出一個簡單dp(i,j) = Min{dp(i-1,j),dp(i,j-1),dp(i,j+1)}+v[i][j].但是你會發覺DP的時候似乎
dp(i,j+1)是在dp(i,j)之后求的..故而必須得雙向DP..
現在考慮第一行的任意一個列都不會去往左右方向走的..因為它如果往左右走的話,則可以直接選擇從左邊或者右邊開始就行.
故可以初始化dp數組
for(int i=1;i<=m;i++)
dp[1][j]=v[1][j];
在考慮dp[i,j]時候.可以這么考慮.
先比較dp[i-1,j]和dp[i-1,j]。通過這個可先求得dp[i][j+1],然后在做一次的dp[i][j+1]的比較..
代碼如下：
#include<iostream>
using namespace std;
int m,n;
int dp[105][505],v[105][505],flag[105][505];
void print(int i,int j)
{
if(i==1)
{
printf("%d\n",j);
return ;
}
if(flag[i][j]==1)
print(i-1,j);
if(flag[i][j]==2)
print(i,j-1);
if(flag[i][j]==3)
print(i,j+1);
printf("%d\n",j);
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&v[i][j]);
for(int j=1;j<=n;j++)
dp[1][j]=v[1][j];
for(int i=2;i<=m;i++)
{
dp[i][1]=dp[i-1][1]+v[i][1];//表示每行第一個房間暫時只能從上邊走下來
flag[i][1]=1; //flag標記 等于1表示從上邊走下
for(int j=2;j<=n;j++) //求從上往下走和從左往右走的最小值
{
dp[i][j]=v[i][j];
if(dp[i-1][j]<dp[i][j-1])
{
dp[i][j]+=dp[i-1][j];
flag[i][j]=1;//flag標記 等于1表示從上邊走到當前位置
}
else
{
dp[i][j]+=dp[i][j-1];
flag[i][j]=2;//flag標記 等于2表示從左邊走到當前位置
}
}
for(int j=n-1;j>=1;j--) //再比較從右往左走的與之前的比較,取更小的.
if(dp[i][j+1]+v[i][j]<dp[i][j])
{
dp[i][j]=dp[i][j+1]+v[i][j];
flag[i][j]=3;//flag標記 等于3表示從右邊走到當前位置
}
}
int Min=0x7fffffff,my;
for(int i=1;i<=n;i++)
if(Min>dp[m][i])
{
Min=dp[m][i];my=i;
}
print(m,my);
return 0;
}posted on 2009-04-03 17:55
米游 閱讀(300)
評論(0) 編輯 收藏 引用 所屬分類:
ACM