题目的意思是..第一行走到第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
米游 阅读(274)
评论(0) 编辑 收藏 引用 所属分类:
ACM