正文 

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

dp斜率优化

wxjor wxjor     2022-08-07     192

关键词：

斜率优化

入门题：PKU3709

很多人貌似都是做这道题来K斜率优化的，所以看了资料以后还是开始入手吧。

然而还是得跪求大神的程序啊 ORZ ORZ……

 

其实理解斜率优化就是会列斜率不等式，还要理解剔除过程。

那么我们来看看这道题：

 

 

                                                 K-Anonymous Sequence
Time Limit: 4000MS   Memory Limit: 65536K
Total Submissions: 5602   Accepted: 1805

Description

The explosively increasing network data in various application domains has raised privacy concerns for the individuals involved. Recent studies show that simply removing the identities of nodes before publishing the graph/social network data does not guarantee privacy. The structure of the graph itself, along with its basic form the degree of nodes, can reveal the identities of individuals.

To address this issue, we study a specific graph-anonymization problem. We call a graph k-anonymous if for every node v, there exist at least k-1 other nodes in the graph with the same degree as v. And we are interested in achieving k-anonymous on a graph with the minimum number of graph-modification operations.

We simplify the problem. Pick n nodes out of the entire graph G and list their degrees in ascending order. We define a sequence k-anonymous if for every element s, there exist at least k-1 other elements in the sequence equal to s. To let the given sequence k-anonymous, you could do one operation only—decrease some of the numbers in the sequence. And we define the cost of the modification the sum of the difference of all numbers you modified. e.g. sequence 2, 2, 3, 4, 4, 5, 5, with k=3, can be modified to 2, 2, 2, 4, 4, 4, 4, which satisfy 3-anonymous property and the cost of the modification will be |3-2| + |5-4| + |5-4| = 3.

Give a sequence with n numbers in ascending order and k, we want to know the modification with minimal cost among all modifications which adjust the sequence k-anonymous.

Input

The first line of the input file contains a single integer T (1 ≤ T ≤ 20) – the number of tests in the input file. Each test starts with a line containing two numbers n (2 ≤ n ≤ 500000) – the amount of numbers in the sequence and k (2 ≤ k ≤ n). It is followed by a line with n integer numbers—the degree sequence in ascending order. And every number s in the sequence is in the range [0, 500000].

 

Output

For each test, output one line containing a single integer—the minimal cost.

 

Sample Input

2
7 3
2 2 3 4 4 5 5
6 2
0 3 3 4 8 9

Sample Output

3
5

很容易想到DP方程：f[i]=MIN{f[j]-sum[j]+sum[i]-a[j+1]*(i-j)}

那么我们可以显然地看出，最优解定然是比所有的解更加优化的。

所以必定存在决策A、B，满足A<B且B更加优于A。

那么我们用A和B带入这个DP方程，可以得到不等式：

f[A]+sum[i]-sum[A]+a[A+1]*(i-A)>= f[B]+sum[i]-sum[B]+a[B+1]*(i-B)

 

两边都有+sum[i],抵消，变为：

f[A]-sum[A]+a[A+1]*(i-A)>= f[B]-sum[B]+a[B+1]*(i-B)

 

把(i-A)与(i-B)拆开，得到：

f[A]-sum[A]+a[A+1]*i-a[A+1]*A>=f[B]-sum[B]+a[B+1]*i-a[B+1]*B

 

移项：

[(f[A]-sum[A]+a[A+1]*A)-(f[B]-sum[B]+a[B+1]*B)]>=i*(a[A+1]-a[B+1])

 

显然，有序序列中a[B+1]>=a[A+1](因为B>A),那么可以化简为：

[(f[A]-sum[A]+a[A+1]*A)-(f[B]-sum[B]+a[B+1]*B)]/(a[A+1]-a[B+1])<=i

 

那么对于a[A+1]=a[B+1]的情况，除法的式子就会没有下线，所以只能用乘法的式子。

如果决策A,B满足上述表达式，则B一定优于A。

难么如果不满足上述表达式B就比A差。

但事实不是这样的，为什么呢？

因为在某些特殊情况下（如成反比）那么随着i的增加不等式的右边是会变小的。

所以在某一个i的位置这个不等式也有可能成立。

 

我们可以令dy(A,B)=(f[A]-sum[A]+a[A+1]*A)-(f[B]-sum[B]+a[B+1])

dx(A,B)=a[A+1]-a[B+1].

 

我们要设置一个队列，队首元素很明显一开始为0

 

然后队列头指针为head，尾指针为tail，如果dy(queue[head],queue[head+1]) >= i*dx(queue[head],queue[head+1]),则队首元素可以直接丢掉，因为如果que[head]没有que[head+1]好，那么以后也不会有它好，所以可以直接丢掉。

 

那么尾部要怎么办呢？

对于两个元素来说，如果对于现在的i，y要比x烂，但是前面已经证明过了，对于比较大的i来说不一定是这样的。那么我们就在加一个元素就直观多了dy(x,y)/dx(x,y)>=dy(y,z)/dx(y,z)那么如果y优于x的话，那么z也一定优于y，无论怎样，它都会被一个更优的元素所代替，这样的话，那么留着y也就没有用了，所以我们可以把它剔除。

 

那么我们可以来考虑一下边界情况，那么dy(x,y)和dy(y,z)有四种极限值方式：INF INF、-INF INF、INF –INF、-INF –INF.那么地1、2、4都满足我们上面推过的式子，但是情况3可就不一样了，在这种情况下，y优于x且y也优于z，明显，按照我们的程序把y剔除掉难道不WA吗？但这种情况不会出现，因为dy(x,y)==0,那么a[x+1]==a[y+1]，则可以在原来的式子中抵消，变为-sum[x]+a[x+1]*x <= -sum[y]+a[y+1]*y，那么如果a[x+1]==a[y+1]，则dy(x,y)一定小于等于0.所以本题可以这样维护求解。

 

我们把过程转化为代码就可以了：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
const int N = 500010;
typedef long long llg;
 
int n, k, queue[N];
llg sum[N], f[N], a[N];
 
llg dy(int j1, int j2)
{
    return  (f[j1]-sum[j1]+a[j1+1]*j1) - (f[j2]-sum[j2]+a[j2+1]*j2);
}
 
llg dx(int j1, int j2)
{
    return  (a[j1+1] - a[j2+1]);
}
 
void dp()
{
    int i, j, head, tail, x, y, z;
    head = tail = 0;
    queue[0] = 0;
    for(i = 1; i <= n; i++)
    {
        while(head<tail && dy(queue[head], queue[head+1])>=i*dx(queue[head], queue[head+1]))
            head++;
        j = queue[head];
        f[i] = f[j] + sum[i] - sum[j] - a[j+1]*(i-j);
        if(i >= 2*k-1)
        {
            z = i-k+1;
            while(head < tail)
            {
                x = queue[tail-1];
                y = queue[tail];
                if(dy(x,y)*dx(y,z) >= dy(y,z)*dx(x,y))  tail--;
                else  break;
            }
            queue[++tail] = z;
        }
    }
}
 
int main()
{
    int t, i;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &k);
        sum[0] = 0;
        for(i = 1; i <= n; i++)
        {
            scanf("%I64d", a+i);
            sum[i] = sum[i-1] + a[i];
        }
        dp();
        printf("%I64d
", f[n]);
    }
    return 0;
}
/*
网上摘抄的代码QAQ
*/

 

斜率优化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]单调！(斜率单调)　　... 查看详情