正文 

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

斜率优化dp

author author     2022-09-14     640

关键词：

前置知识

　　比记号 与 拓展比记号: http://www.cnblogs.com/Sdchr/p/7347799.html

 

[HDU 3507] Print Article 

　　以 [HDU 3507] 来说明清楚斜率优化.

 

　　序列 $s_1, s_2, ..., s_n$ 满足 $s_1 \le s_2 \le ... \le s_n$ .

　　$f_0 = 0$ .

　　$f_i = \min_{0 \le j < i} \left\{ f_j + {(s_i - s_j)} ^ 2 + M \right\}$ .

　　求 $f_n$ .

 

　　$1 \le n <= 500000$ .

　　$0 \le M, c_i \le 1000$ .

 

较优决策点的性质

较优决策点的性质

　　决策点 $k > j$ , $k$ 比 $j$ 优.

 

　　令 $y_i = f_i + s_i ^ 2$ .

　　$[f_j + {(s_i - s_j)} ^ 2 + M, f_k + {(s_i - s_k)} ^ 2 + M] = [(f_j + s_j ^ 2) - (f_k + s_k ^ 2), 2s_i(s_k - s_j)] = [y_k - y_j, 2s_i(s_k - s_j)] < 0$ .

 

　　当 $s_k = s_j$ 时, $y_k < y_j$ .

　　当 $s_k > s_j$ 时, $\frac{y_k - y_j}{s_k - s_j} < 2s_i$ .

 

　　令二维平面上的点 $P_i = (s_i, y_i)$ .

　　当 $s_k = s_j$ 时, $y_k < y_j$ , $P_k$ 在 $P_j$ 下面.

　　当 $s_k > s_j$ 时, $slope(P_k, P_j) < 2s_i$ .

类似的结论

　　$k < j$ , $k$ 比 $j$ 优 $\Leftrightarrow [y_k - y_j, 2s_i(s_k - s_j)] < 0$ .

 

　　类似的, 我们可以得到:

　　当 $s_k = s_j$ 时, $y_k \ge y_j$ , $P_k$ 在 $P_j$ 下面.

　　当 $s_k > s_j$ 时, $slope(P_k, P_j) > 2s_i$ .

 

最优决策点的性质

　　设其中一个最优决策点为 $k$ .

　　过 $k$ 作斜率为 $2s_i$ 的直线 $L$ .

　　根据较优决策点的性质, 以及特判与其余最优决策点的关系, 我们得到:

　　　　对于 $k > j$ , $P_j$ 在 $L$ 上, 或者 $L$ 上方.

　　　　对于 $k < j$ , $P_j$ 在 $L$ 上, 或者 $L$ 上方.

　　所以对于任意 $j$ , $P_j$ 在 $L$ 上, 或者 $L$ 上方.

 

　　最优决策点可能有多个, 但它们一定在一条直线上.

　　如果出现了三点贡献, 那么中间的节点可以不用处理.

　　所以一定有一个最优决策点在下凸壳上.

 

单个问题的解决

　　假设当前我们有所有决策点在二维平面上对应点形成的下凸壳, 那么如何求其中一个最优决策点.

 

　　记下凸壳上的第 $k$ 个点为 $g_k$ .

　　如果过决策点 $g_k$ 作斜率为 $2s_i$ 的直线.

　　我们发现:

　　　　对于最优决策点, 以及最优决策点右边的决策点, $g_kg_{k+1}$ 在 $2s_i$ 对应的方向向量上方.

　　　　对于最优决策点左边的决策点, $g_kg_{k+1}$ 在 $k$ 对应的方向向量下方.

　　等于号可以任意放置.

 

　　我们将 "$g_kg_{k+1}$ 在 $2s_i$ 对应的方向向量上方" , 设置成合法.

　　那么我们目标就是找到合法的最小的坐标, 通过二分即可轻易实现.

 

解法1　　维护下凸壳 + 二分

　　由于 $s_i \ge s_{i-1}$ .

　　所以我们相当于每次在下凸壳的右端插入一个决策点, 然后维护下凸壳, 并用上述方法二分求解即可.

　　时间复杂度为 $O(n \log n)$ .

 

　　实现:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#define F(i, a, b) for (register int i = (a); i <= (b); i++)
#define LL long long
inline LL rd(void) {
    LL f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == ‘-‘) f = -1;
    LL x = 0; for (; isdigit(c); c = getchar()) x = x*10+c-‘0‘; return x*f;
}

const int N = 500005;

int n, M;
LL s[N];

LL f[N];
inline LL T(int Dec, int tar) { return f[Dec] + (s[tar] - s[Dec]) * (s[tar] - s[Dec]) + M; }

struct point {
    LL x, y, id;
    friend inline point operator - (point A, point B) { return (point){A.x - B.x, A.y - B.y, 0}; }
    friend inline LL det(point A, point B) { return A.x * B.y - A.y * B.x; }
}q[N];
int top;

inline void Add(point w) {
    while (top >= 2 && det(w - q[top-1], q[top] - q[top-1]) >= 0)
        q[top--] = (point){0, 0, 0};
    q[++top] = w;
}
inline int Find(point dir) {
    if (top == 1 || det(dir, q[top] - q[top-1]) <= 0) return q[top].id;
    int L = 1, R = top-1;
    while (L < R) {
        int M = (L+R)>>1;
        det(dir, q[M+1] - q[M]) > 0 ? R = M : L = M+1;
    }
    return q[L].id;
}

int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("hdu3507.in", "r", stdin);
    #endif
    
    while (~scanf("%d %d", &n, &M)) {
        memset(s, 0, sizeof s);
        F(i, 1, n) s[i] = s[i-1] + rd();
        
        memset(f, 0, sizeof f), memset(q, 0, sizeof q), top = 0;
        Add((point){s[0], f[0] + s[0] * s[0], 0});
        F(i, 1, n) {
            int Dec = Find((point){1, 2 * s[i], 0});
            f[i] = T(Dec, i);
            Add((point){s[i], f[i] + s[i] * s[i], i});
        }
        printf("%lld\n", f[n]);
    }
    
    return 0;
}

 

斜率优化dp和四边形不等式优化dp整理

...一重循环跑i的所有子状态）这样的时间复杂度是O(N^2)而斜率优化或者四边形不等式优化后的DP可以将时间复杂度缩减到O(N)O(N^2)可以优化到O(N),O(N^3)可以优化到O(N^2),依次类推斜率优化DP和四边形不等式优化DP主要的原理就是利用斜... 查看详情

[dp优化方法之斜率dp]

什么是斜率dp呢大概就把一些单调的分组问题从O(N^2)降到O(N)具体的话我就不多说了看论文:http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html 我自己也补充几句：其实斜率dp有很多种打法有凸包有截距有直接比较斜率的因为我比... 查看详情

斜率优化dp

hihocoder1529不上升序列[斜率优化]Description给出一个序列(a[1...n])，求构造一个(b[1...n])，满足(b_i+1leb_i)，使得(sumlimits_i=1^n|a_i-b_i|)最小.(nle5 imes10^5)Solution关于暴力与转移方程首先对于暴力转移，定义(dp_i,j)为转移到i点，权 查看详情

斜率优化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 查看详情

斜率优化dp

转载自http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html我们知道，有些DP方程可以转化成DP[i]=f[j]+x[i]的形式，其中f[j]中保存了只与j相关的量。这样的DP方程我们可以用单调队列进行优化，从而使得O(n^2)的复杂度降到O(n)。 可... 查看详情

动态规划专题——斜率优化dp

前言斜率优化(DP)是难倒我很久的一个算法，我花了很长时间都难以理解。后来，经过无数次的研究加以对一些例题的理解，总算啃下了这根硬骨头。基本式子斜率优化(DP)的式子略有些复杂，大致可以表示成这样：[f_i=min_j=1^i-1(A(... 查看详情

斜率优化dp学习

转自：http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html我们知道，有些DP方程可以转化成DP[i]=f[j]+x[i]的形式，其中f[j]中保存了只与j相关的量。这样的DP方程我们可以用单调队列进行优化，从而使得O(n^2)的复杂度降到O(n)。 可... 查看详情

hdu2829之二维斜率优化dp

T.E.LawrencewasacontroversialfigureduringWorldWarI.HewasaBritishofficerwhoservedintheArabiantheaterandledagroupofArabnationalsinguerillastrikesagainsttheOttomanEmpire.Hisprimarytargetsweretherailroads 查看详情

hdu2829lawrence(斜率优化dp或四边形不等式优化dp)

...，肯定会超时，就要对其进行优化。有两种方式，一种是斜率对其进行优化，是一个很简单的斜率优化dp[i][j]= min{dp[i- 查看详情

『土地征用landacquisition斜率优化dp』(代码片段)

斜率优化DP的综合运用，对斜率优化的新理解。详细介绍见『玩具装箱TOY斜率优化DP』土地征用LandAcquisition(USACO08MAR)DescriptionFarmerJohnisconsideringbuyingmorelandforthefarmandhashiseyeonN(1<=N<=50,000)additionalrectangularplots,eachwithintegerdimensions(1&l... 查看详情

hdu3507斜率优化dp

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

hdu4258斜率优化dp

CoveredWalkwayTimeLimit:30000/10000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):1496    AcceptedSubmission(s):602ProblemDescript 查看详情

hdu3507斜率优化dp

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

斜率优化第一题！hdu3507|单调队列优化dp

放一手原题 题解：第一次写（抄）斜率优化，心里还是有点小激动的。讲一下怎么实现的！首先我们可以考虑一个朴素的dp：DP[i]表示前i个数字的最少花费，显然我们有一个转移方程DP[i]=min{DP[j]+M+(sum[i]-sum[j])^2}但是N^2肯定会... 查看详情

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

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

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

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

[bzoj3156]防御准备斜率优化dp

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3156裸的斜率优化，记一下以后复习用吧。要直接dp很明显应该要倒着dp，很不爽，先把它倒过来。令$sum[j]=sum_{i=1}^ji$，于是我们首先推出这样一个方程$$f[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*... 查看详情

斜率优化复习小结

这篇基本上还是自己看的，写一些碎片和注意事项 斜率优化：①形如DP[i]=min/max{DP[j]+A[j]+B[j]*C[i]+D[i]+E}方程，将转移方程化为(DP[j]+A[j])=(-C[i])*(B[j])+(DP[i]-D[i]-E)　　即方程斜率式:y=kx+b,其中k=-C[i]　　要求C[i]单调！(斜率单调)　　... 查看详情