[kuangbin带你飞]专题二十 斜率DP

时间：2021-02-24 02:58:46
 
 
   
ID
Origin
Title
  20 / 60 Problem A HDU 3507 Print Article
  13 / 19 Problem B HDU 2829 Lawrence
  1 / 5 Problem C HDU 4528 小明系列故事――捉迷藏
  5 / 6 Problem D HDU 1300 Pearls
  0 / 42 Problem E HDU 2993 MAX Average Problem
  1 / 20 Problem F UVALive 5097 Cross the Wall
  5 / 12 Problem G HDU 3045 Picnic Cows
  2 / 4 Problem H HDU 3516 Tree Construction
  3 / 4 Problem I POJ 1160 Post Office
  3 / 5 Problem J POJ 1180 Batch Scheduling
  3 / 3 Problem K POJ 2018 Best Cow Fences
  2 / 4 Problem L POJ 3709 K-Anonymous Sequence
    Problem M POJ 2841 Navigation Game
  2 / 2 Problem N POJ 1260 Pearls
  2 / 4 Problem O UVA 12594 Naming Babies
  3 / 4 Problem P HDU 3480 Division
  1 / 1 Problem Q UVALive 6771 Buffed Buffet
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

20 / 60 Problem A HDU 3507 Print Article

此题是很基础的斜率DP的入门题。
题意很清楚，就是输出序列a[n]，每连续输出的费用是连续输出的数字和的平方加上常数M
让我们求这个费用的最小值。
设dp[i]表示输出前i个的最小费用，那么有如下的DP方程：
dp[i]= min{ dp[j]+(sum[i]-sum[j])^2 +M } 0<j<i
其中 sum[i]表示数字的前i项和。
相信都能理解上面的方程。
直接求解上面的方程的话复杂度是O(n^2)
对于500000的规模显然是超时的。下面讲解下如何用斜率优化DP使得复杂度降低一维。

我们首先假设在算 dp[i]时，k<j ,j点比k点优。
也就是
dp[j]+(sum[i]-sum[j])^2+M <= dp[k]+(sum[i]-sum[k])^2+M;
所谓j比k优就是DP方程里面的值更小
对上述方程进行整理很容易得到：
[(dp[j]+sum[j]*sum[j])-(dp[k]+sum[k]*sum[k])] / 2(sum[j]-sum[k]) <=sum[i].
注意整理中要考虑下正负，涉及到不等号的方向。
左边我们发现如果令：yj=dp[j]+sum[j]*sum[j] xj=2*sum[j]
那么就变成了斜率表达式：（yj-yk）/(xj-xk) <= sum[i];
而且不等式右边是递增的。
所以我们可以看出以下两点：我们令g[k,j]=(yj-yk)/(xj-xk)
第一：如果上面的不等式成立，那就说j比k优，而且随着i的增大上述不等式一定是成立的，也就是对i以后算DP值时，j都比k优。
那么k就是可以淘汰的。
第二：如果 k<j<i 而且 g[k,j]>g[j,i] 那么 j 是可以淘汰的。
假设 g[j,i]<sum[i]就是i比j优，那么j没有存在的价值
相反如果 g[j,i]>sum[i] 那么同样有 g[k,j]>sum[i] 那么 k比 j优 那么 j 是可以淘汰的

所以这样相当于在维护一个下凸的图形，斜率在逐渐增大。
通过一个队列来维护。

/*

HDU 3507

*/

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN=;

int dp[MAXN];

int q[MAXN];//队列

int sum[MAXN];

int head,tail,n,m;

// dp[i]= min{ dp[j]+M+(sum[i]-sum[j])^2 };

int getDP(int i,int j)

{

    return dp[j]+m+(sum[i]-sum[j])*(sum[i]-sum[j]);

}

int getUP(int j,int k) //yj-yk部分

{

    return dp[j]+sum[j]*sum[j]-(dp[k]+sum[k]*sum[k]);

}

int getDOWN(int j,int  k)

{

    return *(sum[j]-sum[k]);

}

int main()

{

  //  freopen("in.txt","r",stdin);

  //  freopen("out.txt","w",stdout);

    while(scanf("%d%d",&n,&m)==)

    {

        for(int i=;i<=n;i++)

           scanf("%d",&sum[i]);

        sum[]=dp[]=;

        for(int i=;i<=n;i++)

           sum[i]+=sum[i-];

        head=tail=;

        q[tail++]=;

        for(int i=;i<=n;i++)

        {

            //把斜率转成相乘，注意顺序，否则不等号方向会改变的

            while(head+<tail &&  getUP(q[head+],q[head])<=sum[i]*getDOWN(q[head+],q[head]))

               head++;

            dp[i]=getDP(i,q[head]);

            while(head+<tail && getUP(i,q[tail-])*getDOWN(q[tail-],q[tail-])<=getUP(q[tail-],q[tail-])*getDOWN(i,q[tail-]))

                    tail--;

            q[tail++]=i;

        }

        printf("%d\n",dp[n]);

    }

    return ;

}

13 / 19 Problem B HDU 2829 Lawrence

斜率DP

设dp[i][j]表示前i点，炸掉j条边的最小值。j<i

dp[i][j]=min{dp[k][j-1]+cost[k+1][i]}

又由得出cost[1][i]=cost[1][k]+cost[k+1][i]+sum[k]*(sum[i]-sum[k])

cost[k+1][i]=cost[1][i]-cost[1][k]-sum[k]*(sum[i]-sum[k])

代入DP方程

可以得出 y=dp[k][j-1]-cost[1][k]+sum[k]^2

x=sum[k].

斜率sum[i]

可以用斜率优化，也可以用四边形不等式优化，四边形不等式我在前面已经写了。

下面是斜率优化的代码

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAXN=;

int a[MAXN];

int sum[MAXN];

int cost[MAXN];//cost[1][i]

int q[MAXN];

int head,tail;

int n,m;

int dp[MAXN][MAXN];

int DP()

{

    for(int i=;i<=n;i++)

    {

        dp[i][]=cost[i];

        dp[i][i-]=;

    }

    for(int j=;j<=m;j++)

    {

        head=tail=;

        q[tail++]=j;

        for(int i=j+;i<=n;i++)

        {

            while(head+<tail)

            {

                int p1=q[head];

                int p2=q[head+];

                int x1=sum[p1];

                int x2=sum[p2];

                int y1=dp[p1][j-]-cost[p1]+sum[p1]*sum[p1];

                int y2=dp[p2][j-]-cost[p2]+sum[p2]*sum[p2];

                if((y2-y1)<=sum[i]*(x2-x1)) head++;

                else break;

            }

            int k=q[head];

            dp[i][j]=dp[k][j-]+cost[i]-cost[k]-sum[k]*sum[i]+sum[k]*sum[k];

            while(head+<tail)

            {

                int p1=q[tail-];

                int p2=q[tail-];

                int p3=i;

                int x1=sum[p1];

                int x2=sum[p2];

                int x3=sum[p3];

                int y1=dp[p1][j-]-cost[p1]+sum[p1]*sum[p1];

                int y2=dp[p2][j-]-cost[p2]+sum[p2]*sum[p2];

                int y3=dp[p3][j-]-cost[p3]+sum[p3]*sum[p3];

                if((y2-y1)*(x3-x2)>=(y3-y2)*(x2-x1))tail--;

                else break;

            }

            q[tail++]=i;

        }

    }

    return dp[n][m];

}

int main()

{

   // freopen("in.txt","r",stdin);

   // freopen("out.txt","w",stdout);

    while(scanf("%d%d",&n,&m)==)

    {

        if(n==&&m==)break;

        sum[]=;

        cost[]=;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            sum[i]=sum[i-]+a[i];

            cost[i]=cost[i-]+sum[i-]*a[i];

        }

        printf("%d\n",DP());

    }

    return ;

}

c2.这个是先求破坏的最大值

/*

 * 用dp[i][x]表示前i个点，炸掉x条边可以破坏的最大值

 * 答案就是tol-dp[n][m]

 * dp[i][x]=max{dp[j][x-1]+sum[j]*(sum[i]-sum[j])}  x-1<j<i

 * 假设在计算i时，k<j,j比k点优

 * dp[k][x-1]+sum[k]*(sum[i]-sum[k])<=dp[j][x-1]+sum[j]*(sum[i]-sum[j])

 * 化简得 ( (sum[j]*sum[j]-dp[j][x-1])-(sum[k]*sum[k]-dp[k][x-1]) ) /(sum[j]-sum[k]  <=sum[i]

 *

 * yj=sum[j]*sum[j]-dp[j][x-1]    xj=sum[j]

 * (yj-yk)/(xj-xk)<=sum[i]

 * 右边不等式是递增的

 * g[k,j]=(yj-yk)/(xj-xk)

 * 上述不等式成立说明j比k优

 * 如果k<j<i  g[k,j]>g[i,j]那么k可以淘汰

 * 如果g[j,i]<sum[i]  j可以淘汰

 *

 *

 */

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

const int MAXN=;

int n,m;

int a[MAXN];

int sum[MAXN];

int dp[MAXN][MAXN];

int tol;

int getDP(int i,int x,int j)

{

    return dp[j][x-]+sum[j]*(sum[i]-sum[j]);

}

int getUp(int j,int x,int k)

{

    return sum[j]*sum[j]-dp[j][x-]-(sum[k]*sum[k]-dp[k][x-]);

}

int getDown(int j,int k)

{

    return sum[j]-sum[k];

}

int q[MAXN];

void solve()

{

    memset(dp,,sizeof(dp));

    int front,rear;

    for(int x=;x<=m;x++)

    {

        rear=front=;

        q[rear++]=x;

        for(int i=x+;i<=n;i++)

        {

            while(front+<rear && getUp(q[front+],x,q[front])<=sum[i]*getDown(q[front+],q[front]))

                front++;

            dp[i][x]=getDP(i,x,q[front]);

            while(front+<rear && getUp(i,x,q[rear-])*getDown(q[rear-],q[rear-])<=getUp(q[rear-],x,q[rear-])*getDown(i,q[rear-]))

                rear--;

            q[rear++]=i;

        }

    }

    printf("%d\n",tol-dp[n][m]);

}

int main()

{

//    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

    while(scanf("%d%d",&n,&m)==)

    {

        if(n== && m==)break;

        sum[]=;

        for(int i=;i<=n;i++)

        {

            scanf("%d",&a[i]);

            sum[i]=sum[i-]+a[i];

        }

        tol=;

        for(int i=n;i>;i--)

            tol+=a[i]*sum[i-];

        solve();

    }

    return ;

}

1 / 5 Problem C HDU 4528 小明系列故事――捉迷藏
5 / 6 Problem D HDU 1300 Pearls
0 / 42 Problem E HDU 2993 MAX Average Problem
1 / 20 Problem F UVALive 5097 Cross the Wall
5 / 12 Problem G HDU 3045 Picnic Cows
2 / 4 Problem H HDU 3516 Tree Construction
3 / 4 Problem I POJ 1160 Post Office
3 / 5 Problem J POJ 1180 Batch Scheduling
3 / 3 Problem K POJ 2018 Best Cow Fences
2 / 4 Problem L POJ 3709 K-Anonymous Sequence
Problem M POJ 2841 Navigation Game
2 / 2 Problem N POJ 1260 Pearls
2 / 4 Problem O UVA 12594 Naming Babies
3 / 4 Problem P HDU 3480 Division
1 / 1 Problem Q UVALive 6771 Buffed Buffet

相关文章