dp专题 lrj-p269 uva A Spy in the Metro 2003wf

el/2024/2/25 22:46:41

lrj 入门经典  p267

从本题得到的收获:

分清主线:

影响决策的只有时间以及所处的车站

理清次线:

火车跑来跑去的,我们需要处理好他们,为我们的主线服务,即,在某些车站的时候,是否有车在这个时间


故令 dp【】【】,第一维表示时刻,第二维表示在某车站出发,需要等待的时间


写dp就要注意:初始化条件:

这里的初始化条件就是dp【T】【i】为INF,但是在终点(边界),我们却初始化为0,因为递推的方向



#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define INF 0x3f3f3f3f
int time[25];
int dp[300][300];
int has_train[300][300][3];int main()
{int n,t,m1,m2,temp,cases=1;//freopen("in.txt","r",stdin);while(scanf("%d",&n),n!=0){scanf("%d",&t);for(int i=1;i<=n-1;i++)scanf("%d",&time[i]);memset(has_train,0,sizeof(has_train));scanf("%d",&m1);for(int i=1;i<=m1;i++){scanf("%d",&temp);has_train[temp][1][0]=1;for(int j=1;j<=n-1;j++){has_train[temp+time[j]][j+1][0]=1;temp+=time[j];}}scanf("%d",&m2);for(int i=1;i<=m2;i++){scanf("%d",&temp);has_train[temp][n][1]=1;for(int j=n-1;j>=1;j--){has_train[temp+time[j]][j][1]=1;temp+=time[j];}}for(int i=1;i<=n;i++)dp[t][i]=INF;dp[t][n]=0;for(int i=t-1;i>=0;i--){for(int j=1;j<=n;j++){dp[i][j]=dp[i+1][j]+1;if(j<n&&has_train[i][j][0]&&i+time[j]<=t)dp[i][j]=min(dp[i][j],dp[i+time[j]][j+1]);if(j>1&&has_train[i][j][1]&&i+time[j-1]<=t)dp[i][j]=min(dp[i][j],dp[i+time[j-1]][j-1]);}}printf("Case Number %d: ",cases++);if(dp[0][1]>=INF) puts("impossible");else              printf("%d\n",dp[0][1]);}return 0;
}



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

相关文章

uva 437 动态规划 lrj - P269

题意&#xff1a; 给出不超过30个立方体&#xff0c;每一种有无穷多个。 要求这些立方体堆成一个尽量搞的柱子&#xff0c;使得每一个立方体下面的立方体的底面长宽都大于上面的底面长宽 题解&#xff1a; 很明显我们可以将每个立方体当做3个或者6个不一样的不可以旋转的…

uva 1347 动态规划DAG lrj-P269

题意&#xff1a; 给出按照 x 坐标排序的一系列二维坐标上的点&#xff0c;让你通过来回走一圈&#xff0c;把所有点都恰好走一遍&#xff0c;除了最左端和最右端的点 使得总路程最短 题解&#xff1a; 让两个人同时走&#xff0c;并且不重合&#xff0c;从左边开始走道…

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

题意&#xff1a; 给定一个n*m的矩阵&#xff0c;要求从第一列的任何一行出发&#xff0c;每次沿右或右下或右上到达后面一列&#xff0c;最后到第m列任何一行整个路程的最小值&#xff0c;并且要求是字典序最小的 题解&#xff1a; 动态规划 每一列是一个阶段&#xff…

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…