正文 

当前位置： 首页 > java > java教程

hdu3507单调队列斜率优化

(mLweleth) (mLweleth)     2022-09-18     206

关键词：

斜率优化的模板题

给出n个数以及M，你可以将这些数划分成几个区间，每个区间的值是里面数的和的平方+M，问所有区间值总和最小是多少。

如果不考虑平方，那么我们显然可以使用队列维护单调性，优化DP的线性方法来做，但是该题要求的是区间和的平方，于是要转换单调的计算方法为斜率，也就是凸线。

其他就是最基本的单调DP

/** @Date    : 2017-09-04 15:39:05
  * @FileName: HDU 3507 单调队列 斜率优化 DP.cpp
  * @Platform: Windows
  * @Author  : Lweleth ([email protected])
  * @Link    : https://github.com/
  * @Version : $Id$
  */
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8;

int n, m;
int a[5*N];
LL dp[5*N];
LL sum[5*N];

LL XX(int a, int b)
{
	return dp[b] + sum[b] * sum[b] - (dp[a] + sum[a] * sum[a]); 
}

LL YY(int a, int b)
{
	return 2 * (sum[b] - sum[a]);
}
int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		MMF(sum);
		MMF(dp);
		for(int i = 1; i <= n; i++)
		{
			scanf("%d", a + i);
			sum[i] = sum[i - 1] + a[i];
		}

		deque<int>q;
		q.push_back(0);
		for(int i = 1; i <= n; i++)
		{
			auto pos = q.begin();
			while(q.size() > 1 && XX(*pos, *(pos + 1)) <= sum[i] * YY(*pos, *(pos + 1)))
				q.pop_front(), pos = q.begin();
			if(!q.empty())
				dp[i] = dp[q.front()] + (sum[i] - sum[q.front()])*(sum[i] - sum[q.front()]) + m;
			//cout << dp[i] << endl;
			pos = q.end();
			while(q.size() > 1 && XX(*(pos - 2), *(pos - 1)) * YY(*(pos - 1), i) >= XX(*(pos - 1), i) * YY(*(pos - 2), *(pos - 1)))
			{
				q.pop_back();
				pos = q.end();
			}
			q.push_back(i);
		}
		printf("%lld
", dp[n]);
	}
    return 0;
}

hdu3507printarticle（斜率优化）(代码片段)

显然的斜率优化模型但是单调队列维护斜率单调性的时候出现了莫名的锅orz代码#include<cstdio>#include<algorithm>#include<cstring>#include<deque>#defineintlonglongusingnamespacestd;inta[500100],dp[500100],n,m,sum[500100],q[500100],h=1,t=0;intf(intx)... 查看详情

hdu3507printarticle（斜率优化）

HDU3507PrintArticle（斜率优化）ACM题目地址： HDU3507PrintArticle题意： 给定一个长度为n的序列。和一个常数m，我们能够将序列分成任意段，每段的权值为sum(arr[i])+C(x<=i<=y)，求一种划分方法使得整个序列的权值最小分析：&... 查看详情

[hdu3507]斜率优化dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3507kuangbin大佬的博客讲的非常清楚orzhttp://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll 查看详情

hdu3507printarticle（斜率优化入门）（pascal）

ProblemDescriptionZerohasanoldprinterthatdoesn‘tworkwellsometimes.Asitisantique,hestillliketouseittoprintarticles.Butitistoooldtoworkforalongtimeanditwillcertainlywearandtear,soZerouseacosttoevaluatet 查看详情

hdu3507斜率优化dp

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):11141    AcceptedSubmission(s):3393ProblemDescription 查看详情

hdu3507斜率优化dp

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):12185    AcceptedSubmission(s):3733ProblemDescription 查看详情

hdu3507printarticle（斜率dp优化）(代码片段)

ProblemDescriptionZerohasanoldprinterthatdoesn‘tworkwellsometimes.Asitisantique,hestillliketouseittoprintarticles.Butitistoooldtoworkforalongtimeanditwillcertainlywearandtear,soZerouseacosttoevaluatet 查看详情

hdu3507printarticle(斜率优化dp)

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):12824    AcceptedSubmission(s):3967ProblemDescription 查看详情

hdu3507printarticle（斜率优化）(代码片段)

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):15536    AcceptedSubmission(s):4813ProblemDescription 查看详情

hdu3507printarticle(经典斜率优化dp)(代码片段)

...样移向？因为常见的优化就只有几种，例如四边形优化，单调队列优化，斜率优化，这个初始的式子中有两个变量，还是成对出现的我们就可以猜测可以表达成斜率，当然这也是一种经验。所以满足这个情况的k是不满足的当前i... 查看详情

hdu3507printarticle（斜率优化dp）

...000）解题思路：参考了这里的思路，这算是我写得第一题斜率优化DP了，当做模板来用吧。推理下次补 查看详情

hdu3507printarticle（斜率优化）

...(dp[i]=min{dp[j]+(S[i]-S[j])^2+M},j<i)(O(n^2))是过不了50万的，用斜率优化设有(k<j<i)使 查看详情

hdu3507printarticle[斜率优化dp入门题]

PrintArticleTimeLimit:9000/3000MS(Java/Others)    MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):11761    AcceptedSubmission(s):3586ProblemDescription 查看详情

hdu3507printarticle（斜率优化）(代码片段)

...连续输出一段，问输出所有数的总价值最小是多少思路：斜率优化，但我不知道为什么写成slop就不对，可怜我的斜率优化板子，又要该了，其他没什么，简单的推一下是下凸包，没什么其他的了代码：#include<set>#include<map&... 查看详情

hdu3507printarticle——斜率优化dp(代码片段)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=3507设f[i]，则f[i]=f[j]+(s[i]-s[j])*(s[i]-s[j])+m即f[j]+s[j]*s[j]=2*s[i]*s[j]+f[i]-s[i]*s[i]-m于是维护下凸包即可；写成double的slp总是不对，把分母乘到对面就对了...代码如下：#include<iostream 查看详情

hdu3507：printarticle（斜率优化dp）(代码片段)

...与\(i,j\)两个变量有关，这种一般可以考虑分离变量然后斜率dp优化。(P 查看详情

hdu3507[printarticle]dp斜率优化(代码片段)

题目大意给定一个长度为(n(nleqslant500000))的数列，将其分割为连续的若干份，使得$sum((sum_i=j^kC_i)+M)$最小。其中(C_i)为序列中的项的值，(M)为常数。$j,k$表示在原序列中连续的某一段的起始位置和结束位置。解题思路考虑到(n)的范... 查看详情

斜率优化dp

前置知识　　比记号与拓展比记号: http://www.cnblogs.com/Sdchr/p/7347799.html [HDU3507]PrintArticle 　　以[HDU3507]来说明清楚斜率优化. 　　序列$s_1,s_2,...,s_n$满足$s_1les_2le...les_n$.　　$f_0=0$.　　$f_i=min_{0le 查看详情