Hurdles of 110m ZOJ - 2972 (动态规划)

怼烎@ 2022-05-27 12:46 145阅读 0赞

#include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const double ep=1e-10;
    const int INF=0x3f3f3f3f;
    int n, m;
    
    struct node {
    	int t1, t2, t3, c1, c2;
    } lan[120];
    
    int dp[120][120];
    
    int main() {
    	int T;
    	scanf("%d", &T);
    	while(T--) {
    		memset(dp, 0x3f, sizeof(dp));
    		scanf("%d%d", &n, &m);
    
    		for(int i=1; i<=n; i++)
    			scanf("%d%d%d%d%d", &lan[i].t1, &lan[i].t2, &lan[i].t3, &lan[i].c1, &lan[i].c2);
    
    		dp[0][m]=0;
    
    		for(int i=1; i<=n; i++) {
    			for(int j=0; j<=m; j++) {
    				
    				if(m>=j+lan[i].c1)
    					dp[i][j]=min(dp[i][j], dp[i-1][j+lan[i].c1]+lan[i].t1);
    				
    				dp[i][j]=min(dp[i][j], dp[i-1][j]+lan[i].t2);
    
    				/*if(j-lan[i].c2>=0)//很奇怪，不知道为什么用慢跑跟新的时候，被注释掉的部分这样写是不行的。
    				{
    					if(j==m)
    					{
    						for(int k=m-lan[i].c2; k<=m; k++)
    							dp[i][m]=min(dp[i][m], dp[i-1][k]+lan[i].t3);
    					}	
    					else
    						dp[i][j]=min(dp[i][j], dp[i-1][j-lan[i].c2]+lan[i].t3);
    				}*/
    				int tmp=min(m, j+lan[i].c2);
    				dp[i][tmp]=min(dp[i][tmp], dp[i-1][j]+lan[i].t3);
    					
    			}
    		}
    		int ans=INF;
    		for(int i=0; i<=m; i++)
    			ans=min(dp[n][i], ans);
    		printf("%d\n", ans);
    	}
    
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关【中等】拼 M 面值硬币问题（动态规划）

题目 > 现在有 n1 + n2 种面值的硬币，n1 种为普通面值硬币，可以随意取用。n2 种为纪念币，每种最多只能取一个。每种硬币有一个面值，问：凑满 M 面值有多少种

一时失言乱红尘/ 2022年09月10日 12:11/ 0 赞/ 176 阅读

相关 Hurdles of 110m ZOJ - 2972 (动态规划)

include<cstdio> include<cmath> include<cstring> include<algorithm> u

怼烎@/ 2022年05月27日 12:46/ 0 赞/ 146 阅读

相关 ZOJ - 3777 && ZOJ - 2972（dp )

这两个dp感觉非常类似，都是dfs会超时，利用上一层和下一层关系， dp做出来 zoj 2972 include<cstdio> includ

待我称王封你为后i/ 2022年05月26日 03:39/ 0 赞/ 217 阅读

相关动态规划

等我有时间了，一定要把《算法导论》啃完，这本书的印刷质量实在太好了，就是烧脑子，滑稽。适合应用动态规划求解的最优化问题应该具备两个要素：最优子结构：一个问题的最优解包含

短命女/ 2022年05月17日 09:45/ 0 赞/ 325 阅读

相关动态规划之最小M段和问题

\include <stdio.h> \include <stdlib.h> \define MAX(a,b) a>b?a:b int a\[100\]; int

骑猪看日落/ 2022年04月22日 02:14/ 0 赞/ 493 阅读

相关 zoj 2676 网络流+01分数规划

题意：有一个n个点的网络，其中有m条光缆（所有的点都被连接，任意两个点之间最多有一条，不存在连接自身的），每条光缆有一定的价值，网络中1为起点，n为终点，现在要求找出一些光缆

傷城~/ 2022年01月11日 01:57/ 0 赞/ 374 阅读

相关 ZOJ 1109 Language of FatMouse

We all know that FatMouse doesn't speak English. But now he has to be prepared since our

忘是亡心i/ 2021年12月11日 11:29/ 0 赞/ 191 阅读

相关 ZOJ 2972 Hurdles of 110m 【DP 背包】

一共有N段过程，每段过程里可以选择快速跑、匀速跑和慢速跑对于快速跑会消耗F1 的能量，慢速跑会集聚F2的能量选手一开始有M的能量，即能量上限求通过全程的最

Dear 丶/ 2021年12月10日 16:45/ 0 赞/ 241 阅读

相关动态规划

算法题中动态规划是真的难，写一篇总结，彻底解决动态规划。参考：[https://blog.csdn.net/u013309870/article/details/7519359

左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 496 阅读

相关 ICP Registration: Smoothing the Hurdles of Chinese Web Hosting

China has a system of regulating websites which requires every commercial website hos...

红太狼/ 2021年04月24日 03:34/ 0 赞/ 293 阅读