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

el/2024/2/25 0:31:53

题意:

给定一个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;
}



http://www.ngui.cc/el/4895177.html

相关文章

uva 12563 01背包 两个最优条件 lrj-P274

题意&#xff1a; 给你 t 秒时间&#xff0c;有n首歌&#xff0c;每一首歌的时间不超过三分钟&#xff0c;在结束之前唱一首678秒的劲歌金曲 选了一首歌就一定要唱完 并且在保持唱的歌曲数量最多的情况下&#xff0c;时间最长 题解&#xff1a; 虽然 t 的范围很大&…

uva 11400 lrj-P275 动态规划

题意&#xff1a; 见刘汝佳入门书籍 P275 dp[i]min(dp[i],dp[j-1](sum[i]-sum[j-1])*a[i].ca[i].k);题解&#xff1a; 见刘汝佳入门书籍 P275 #include<stdio.h> #include<string.h> #include<algorithm> using namespace std;int dp[1010],sum[1010]; s…

密码生成器+随机数生成器

随机数生成器 0~RAND_MAX之间的随机数程序 #include <iostream> #include <stdlib.h> #include <time.h> using namespace std; int main() {srand((unsigned)time(NULL));for(int i = 0; i < 10; i++ )cout << rand() << \t;cout << …

uva 10003 lrj-P278 区间dp入门

题意&#xff1a; 给出一根棍子的长度&#xff0c;以及n个需要切割的点&#xff0c;每一次切割的代价是这一段需要被切割的长度 问代价最小时的代价值 题解&#xff1a; 区间dp dp[i][j]min(dp[i][j],dp[i][k]dp[k][j]a[j]-a[i]); i 为区间左端点&#xff0c;j 为右端点…

Uva-1626 lrj-P278 区间dp

题意&#xff1a; 给定一个由[,],(,)&#xff0c;构成的字符串&#xff0c;给其添加这些括号使得其成为一个正规括号序列 1 空序列是正规括号序列 2 如果S是正规括号序列&#xff0c;那么[S]和(S)也是正规括号序列 3 如果A和B都是正规括号序列&#xff0c;则AB也是正规…

uva 1331 lrj-P279 三角剖分+区间dp

题意&#xff1a; 给出多边形&#xff0c;找出最大三角形面积最小的三角剖分 输出最大的三角形面积 题解&#xff1a; 仔细研究可以知道&#xff0c;第一个点和最后一个点组成的边&#xff0c;一定是在某一个三角形中 那么我们就通过这个边作为基准&#xff0c;任选一个…

uva 12186 lrj-P282 简单树形dp

题意&#xff1a; 某个人签字的话,他的直属下属里必须有至少T%的人签字,问让老板签字最少需要多少工人签字 题解&#xff1a; 树形dp 以老板为根节点&#xff0c;从小往上&#xff0c;递归计算答案即可 #include<vector> #include<stdio.h> #include<st…

uva 1220 lrj-P282 最大独立集(树形dp)

题意&#xff1a; 给出一个树形结构&#xff0c;除了老板外&#xff0c;每一个员工都有直属上司&#xff0c;在其中挑选了员工&#xff0c;就不能挑选他的上司 问这样的挑选方法最多可以挑选多少人&#xff0c;方案是否唯一 题解&#xff1a; 仔细划分即可 当前节点若选…

uva 10285 lrj-P304 从简单DAG动态规划得到的感悟

题意&#xff1a; 给出一个整数矩阵&#xff0c;请找出一条严格递减的最长路的长度 题解&#xff1a; 分析&#xff1a; 1没有固定起点和终点 2是二元关系&#xff0c;也就是DAG&#xff08;有向无环图&#xff09; 3lrj书上此类一律都是用记忆化搜索 假设&#xff…

uva 1630 lrj-P305 字符串dp(记忆化)

题意&#xff1a; 给出一个字符串&#xff0c;然后要你把他折叠成一个最短的字符串 例如 AAAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES 变成&#xff1a; 9(A)3(AB)CCD 2(NEERC3(YES) 题解&#xff1a; 很容易看出来用分治的办法&#xff0c;但是不会把折叠起来&a…