动态规划 -----入门练习1

末蓝、 2022-04-17 03:49 250阅读 0赞

现在1~Q个时间段内有n（n<100）个工作，每个工作都有各自的开始时间start，结束时间end和工作所得钱p,工作时间有重叠 ，现问在这段时间内所得钱最多为多少？

输入：

8
    1 4 5
    3 5 1
    0 6 8
    4 7 4
    3 8 6
    5 9 3
    6 10 2
    8 11 4

输出：

13

#include<iostream>
    using namespace std;
    typedef struct{//结构体 
    	int start;//开始时间 
    	int end;//结束时间 
    	int p;//该任务所得钱 
    }page;
    int n;//任务个数 
    page a[100];//方案数组 
    int perv[100];//存放前一个选择方案 
    void perv_page(int n)//前面最近可以选择哪个方案 
    {
    	int t;
    	for(int i=1;i<=n;i++)
    	{
    		t=0;
    		for(int j=1;j<=n;j++)
    		{
    			if(a[j].end<=a[i].start){
    				t=j;continue;
    			}	  
    		}
    		perv[i]=t;
    	}
    }
    /*int f(int i){//非记忆化 
    	if(i==0) return 0;
    	else
    	 return max(f(i-1),f(perv[i])+a[i].p);
    }*/ 
    int value[100]={0};//存放每次的最佳方案 
    int f(int i)//记忆化 
    {
    	if(i==0) return 0;
    	if(value[i]!=0) return value[i];
    	return value[i]=max(f(i-1),f(perv[i])+a[i].p);
    }
    int main(){
    	cin>>n;//输入方案数 
    	for(int i=1;i<=n;i++)
    	 cin>>a[i].start >>a[i].end >>a[i].p;
    	 a[0].p=0;
    	 
    	perv_page(n);
    //	for(int i=1;i<=n;i++) //测试存放数组 0 0 0 1 0 2 3 5 
    //	 cout<<perv[i]<<endl;
         
         f(n);
         /*for(int i=1;i<=n;i++){ //测试每次的最佳方案5 5 8 9 9 9 10 13 
    	    cout<<value[i]<<endl; 
    	 } */
         cout<<value[n]<<endl;//最佳方案 
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划基础入门【1】

动态规划基础入门 1 基础概念 2 经典题目 > 诀窍：常规递归 -> 缓存表 -> 动态规划 > 需要有一个尝试的过程 2.1 机器人走的方法数

╰+哭是因爲堅強的太久メ/ 2024年04月07日 12:50/ 0 赞/ 88 阅读

相关动态规划练习（1）印章

四大步骤：一：确定状态最后一步化成子问题二：状态转移写出表达式三：初始条件和边界情况四：计算顺序

矫情吗；*/ 2023年09月28日 19:59/ 0 赞/ 19 阅读

相关 Open Judge——动态规划练习

目录了解动态规划 2760:数字三角形 1、题目 2、代码 4120:硬币 1、题目 2、代码 -------------------- 了解动态规划

刺骨的言语ヽ痛彻心扉/ 2023年09月27日 22:44/ 0 赞/ 116 阅读

相关算法刻意练习之动态规划

1 特点 1.1 动态规划和递归或者分治没有根本上的区别（关键看有无最优的子结构) 1.共性:找到重复子问题； 2.差异性:最优子结构、中途可以淘太欠优解；

我不是女神ヾ/ 2022年12月21日 06:25/ 0 赞/ 207 阅读

相关动态规划（1）

转自：http://cppblog.com/menjitianya/archive/2015/10/23/212084.html 建议去支持原文目录一、动态规划初

淩亂°似流年/ 2022年12月15日 15:27/ 0 赞/ 237 阅读

相关动态规划（练习题目，）

[http://www.cnblogs.com/lzmfywz/archive/2012/02/15/2353320.html][http_www.cnblogs.com_lz

男娘i/ 2022年09月18日 00:52/ 0 赞/ 247 阅读

相关动态规划入门篇

动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。首先，我们看一下这

深碍√TFBOYSˉ_/ 2022年06月10日 12:45/ 0 赞/ 271 阅读

相关动态规划练习

这一天zdw说了一个很长的字符串，只包括 ‘y’ , ‘i’ , ‘n’ ,’g’这四个字符。你需要选取尽量多的下标，让这些下标在这个字符串中对应的字符按下标从小到大的顺序组起

淩亂°似流年/ 2022年05月10日 14:10/ 0 赞/ 181 阅读

相关动态规划-------入门练习2

题目一：假设有n个数从n个数中找出任意个不相邻的数求和计算出这个和的最大值输入： 5 4 1 1 9 1 输出： 13 （最好的方案为4+

比眉伴天荒/ 2022年04月17日 04:51/ 0 赞/ 238 阅读

相关动态规划 -----入门练习1

现在1~Q个时间段内有n（n<100）个工作，每个工作都有各自的开始时间start，结束时间end和工作所得钱p,工作时间有重叠，现问在这段时间内所得钱最多为多少？

末蓝、/ 2022年04月17日 03:49/ 0 赞/ 251 阅读