HDU 1024(DP+滚动数组优化)

2024-04-18 07:08
文章标签 数组 dp 优化 hdu 滚动 1024

本文主要是介绍HDU 1024(DP+滚动数组优化),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:点击打开链接


题目大意:给一个m和一个n,n表示有n个数字,m表示有m种区间和,每个区间之间不能相互交叉,问你最大的m个区间和加起来最大是多少。


题目思路:DP是我目前非常非常薄弱的方面QAQ,于是这道题足足花了我三个小时....看了一大堆的博客,终于貌似应该会了QAQ。直接上滚动数组难以理解,我先从二维的角度来讲一下这个题目思路。首先定义一个dp[i][j],表示i段j个数字的最大和是多少。对这种情况,动态转移方程为dp[i][j]=max{f[i][j-1]+a[j],f[i-1][k]+a[j],(i-1<=k<j)} (i<=j<=n),因为对于第i段j个数字,他的大小只取决于前面的两个情况,一个是他直接接到i段j-1个数字后面,即跑到原来第i段的最后,还有一种情况就是跑到前j-1个数字中所有段中最大的情况,这就是题目中提到的k,然后自己当老大,开辟新纪元(当一个新段的头)。但是对于这种情况有一个弊端,题目中给的数据范围是n<=1000000,如果你开一个这么大的二维数组,铁定炸了,所以要用滚动数组来优化,将其降维成一个一维的问题。

滚动数组篇:其实你自己观察会发现,你实际上推出当前状态需要用到的数据,只有两个, 一个是i段j-1个数字能取到的最大值,一个是前j-1个数字除i段以外其他段能取到的最大值。然后外面第一层for循环,来表示分成几段。用a[i]来存原始数组,用maxx[i]来存前j-1个数字除i段以外其他段能取到的最大值,用max1来存当前情况下的dp最大值(用来传给maxx数组),现在开始仔细说明流程。dp[j]数组必须从i开始更新,即至少要等于段数,为什么捏,因为你要是n-1个数怎么分成n段..所以要从i开始,然后一直到头,全部按照我们的要求来更新,maxx数组又是咋变的呢?每一轮过来的时候,maxx[j-1]先等于max1(该数组其实是上一次存下来的),然后更新max1,让max1跟dp[j]比较。这么做是为了获得前j-1个数字除i段以外其他段能取到的最大值。然后这次获得的max1传送给下一个循环的maxx[j]。


以下是代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int a[1000005],dp[1000005],maxx[1000005],max1;
int main(){int n,m;while(~scanf("%d%d",&m,&n)){memset(dp,0,sizeof(dp));memset(maxx,0,sizeof(maxx));for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=m;i++){max1=-inf;for(int j=i;j<=n;j++){dp[j]=max(dp[j-1],maxx[j-1])+a[j];maxx[j-1]=max1;max1=max(max1,dp[j]);}}printf("%d\n",max1);}return 0;
}

这篇关于HDU 1024(DP+滚动数组优化)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/914089

相关文章

Vue3 的 shallowRef 和 shallowReactive:优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉,那么对 shallowRef 和 shallowReactive 是否了解呢? 在编程和数据结构中,“shallow”(浅层)通常指对数据结构的最外层进行操作,而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素,而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层(Shallow) 定义

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO