uva 116 动态规划 多阶段决策问题 路径记录 lrj-P270

本文主要是介绍uva 116 动态规划 多阶段决策问题 路径记录 lrj-P270，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给定一个n*m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的

题解：

动态规划

每一列是一个阶段，一个阶段有三个决策，逆推可以方便的记录路径然后顺着打印出来

字典序最小很巧妙的利用排序解决了

需要注意的是m==1的情况，所以下面的双 if  不能用 if  else if

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define INF 0x3f3f3f3f
int a[110][110],dp[110][110],nexts[110][110];int main()
{int n,m;//freopen("in.txt","r",stdin);while(scanf("%d%d",&m,&n)!=EOF){for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){scanf("%d",&a[i][j]);nexts[i][j]=0;}}int ans=INF,frist=1;for(int j=n;j>=1;j--){for(int i=1;i<=m;i++){if(j==n) dp[i][j]=a[i][j];else{int row[3]={i,i-1,i+1};if(i==1)      row[1]=m;if(i==m)      row[2]=1;sort(row,row+3);dp[i][j]=INF;for(int k=0;k<3;k++){int v=dp[row[k]][j+1]+a[i][j];if(v<dp[i][j])  dp[i][j]=v, nexts[i][j]=row[k];}}if(j==1&&dp[i][j]<ans) ans=dp[i][j],frist=i;}}printf("%d",frist);for(int i=nexts[frist][1],j=2;j<=n;i=nexts[i][j],j++)printf(" %d",i);printf("\n%d\n",ans);}return 0;
}

这篇关于uva 116 动态规划 多阶段决策问题 路径记录 lrj-P270的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---