首页 > 代码库 > HDU5092
HDU5092
题意:找出从第1层到第n层的路径使得路径上的点和最小,若有多条选择最右的。
DP
#include<iostream>#include<cstdio>using namespace std;const long long NO=106;const long long INF=100000000000000000LL;long long n,m;long long MAP[NO][NO];long long pre[NO][NO];long long dp[NO][NO];void dfs(long long i,long long j){ if(i==1) { printf("%I64d",j); return; } dfs(i-1,pre[i][j]); printf(" %I64d",j);}int main(){ long long ttt,cas=1; scanf("%I64d",&ttt); while(ttt--) { printf("Case %I64d\n",cas++); scanf("%I64d%I64d",&n,&m); for(long long i=1;i<=n;i++) for(long long j=1;j<=m;j++) scanf("%I64d",&MAP[i][j]); for(long long i=1;i<=n;i++) dp[i][0]=dp[i][m+1]=INF; for(long long i=0;i<=n;i++) for(long long j=1;j<=m;j++) { dp[i][j]=dp[i-1][j+1]; pre[i][j]=j+1; if(dp[i][j]>dp[i-1][j-1]) { dp[i][j]=dp[i-1][j-1]; pre[i][j]=j-1; } if(dp[i][j]>dp[i-1][j]) { dp[i][j]=dp[i-1][j]; pre[i][j]=j; } dp[i][j]+=MAP[i][j]; } long long MIN=INF; long long s=m; for(long long j=m;j;j--) if(MIN>dp[n][j]) MIN=dp[n][j],s=j; dfs(n,s); puts(""); } return 0;}
HDU5092
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。