[1444] The Waterfall Flow

• [1444] The Waterfall Flow

  • • • • • 　　　　　　　　　　http://ac.nbutoj.com/Problem/view.xhtml?id=1444
• 时间限制: 1000 ms　内存限制: 65535 K
• 问题描述
• The Hero is on the way to beat the Devil, now he comes near to a waterfall flow.
  The Devil puts a magic on the waterfall flow in order to stop the Hero.
  
  The magic makes the waterfall flow come into being m * n (m lows and n columns) blocks, each block is bound with a number Hi, it means that if the Hero comes into that block, he will be injured by Hi HP.
  
  Now, the Hero wants to kill the Devil, he must go from the foot of the waterfall flow to the top of it. The Hero can choose one of n foot blocks to selected as the starting point, and he can only go upward and towards the left, as well as the right.
  
  To kill the Devil, he must left more and more HP, can you help him?
  
  
• 输入
• Input until EOF.
  Each test will contain two integers m and n (3 <= m, n <= 20), and a m * n matrix. The matrix includes m * n integers Hi (1 <= Hi <= 1000).
  
• 输出
• A line includes a integer with the injured HP.
  
• 样例输入

• 4 3
  1 2 3
  4 5 6
  7 8 9
  10 11 12
  4 3
  1000 1000 1
  1 1 1
  1 1000 1000
  1 1 1
  

• 样例输出

• 22
  6
  

• 提示

• 无

• 来源

• Hungar

• 操作

简单DP,一个状态dp(i,j) 由左右下,三个方向传递而来,所以dp(i,j) = min( dp(i,j-1), dp(i,j+1), dp(i-1,j) ) + cost(i,j)

#include
#include
#includeusing namespace std;const int INF=0x3f3f3f3f;int m,n;
int dp[25][25];
int val[25][25];int main(){//freopen("input.txt","r",stdin);while(~scanf("%d%d",&m,&n)){memset(dp,0x3f,sizeof(dp));memset(val,0x3f,sizeof(val));int i,j;for(i=1;i<=m;i++)for(j=1;j<=n;j++){scanf("%d",&val[i][j]);}for(i=1;i<=n;i++)dp[m][i]=val[m][i];for(i=m-1;i>=1;i--){for(j=1;j<=n;j++)dp[i][j]=dp[i+1][j]+val[i][j];for(j=2;j<=n;j++)dp[i][j]=min(dp[i][j],dp[i][j-1]+val[i][j]);for(j=n-1;j>=1;j--)dp[i][j]=min(dp[i][j],dp[i][j+1]+val[i][j]);}int ans=INF;for(j=1;j<=n;j++)if(ans>dp[1][j])ans=dp[1][j];printf("%d\n",ans);}return 0;
}

转载于:https://www.cnblogs.com/jackge/archive/2013/04/30/3052584.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！