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

末蓝、 2022-04-17 03:49 334阅读 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 条评论，334人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

相关 DP动态规划入门学习--1

DP经典问题（选或不选）题目搬自：[https://www.bilibili.com/video/av18512769/][https_www.bilibili.com

朱雀/ 2023年07月13日 03:20/ 0 赞/ 86 阅读

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

故事开始以前最初的那些春天阳光洒在杨树上风吹来闪银光街道平静而温暖钟走得好慢那是我还不识人生之味的年代我情窦还不开你的衬衣如雪盼着杨树叶

た入场券/ 2023年07月03日 06:05/ 0 赞/ 48 阅读

相关动态规划问题练习

1.是否能通过考试 Description 小张想要通过明天的考试。他知道考题的分值分布，也知道考试中要拿到每一个题目需要耗费的时间。假设考试时长为h，共n个题目，需要拿到

偏执的太偏执、/ 2023年06月15日 10:00/ 0 赞/ 37 阅读

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

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

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

相关动态规划练习

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

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

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

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

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

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

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

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