hdu 3507 Print Article (斜率优化dp)

Posted by 111qqz on Saturday, September 24, 2016

TOC

题目链接

题意:n个数,分成若干段,每段的代价为
,求最小代价。

思路:dp。

状态方程很显然个鬼。。。

dp[i] 表示处理完前面i个数的最小代价。

dp[0] = 0 ;

dp[i] = min(dp[j]+(sum[i]-sum[j])^2) ( 0<j <i),sum[i]为a[i]的前缀和。

这复杂度是n^2的。。。然而n最大5E5…..boom….

斜率优化登场!

这篇博客讲得非常好

两边移项一下,得到:(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我们把dp[j]-num[j]^2看做是yj,把2*num[j]看成是xj。

那么不就是yj-yk/xj-xk<sum[i]么?   左边是不是斜率的表示?

那么yj-yk/xj-xk<sum[i]说明了什么呢?  我们前面是不是假设j的决策比k的决策要好才得到这个表示的? 如果是的话,那么就说明g[j,k]=yj-jk/xj-xk<sum[i]代表这j的决策比k的决策要更优。

关键的来了:现在从左到右,还是设k<j<i,如果g[i,j]<g[j,k],那么j点便永远不可能成为最优解,可以直接将它踢出我们的最优解集。为什么呢?

我们假设g[i,j]<sum[i],那么就是说i点要比j点优,排除j点。

如果g[i,j]>=sum[i],那么j点此时是比i点要更优,但是同时g[j,k]>g[i,j]>sum[i]。这说明还有k点会比j点更优,同样排除j点。

排除多余的点,这便是一种优化!

接下来看看如何找最优解。

设k<j<i。

由于我们排除了g[i,j]<g[j,k]的情况,所以整个有效点集呈现一种上凸性质,即k j的斜率要大于j i的斜率。

这样,从左到右,斜率之间就是单调递减的了。当我们的最优解取得在j点的时候,那么k点不可能再取得比j点更优的解了,于是k点也可以排除。换句话说,j点之前的点全部不可能再比j点更优了,可以全部从解集中排除。

于是对于这题我们对于斜率优化做法可以总结如下:

1,用一个单调队列来维护解集。

2,假设队列中从头到尾已经有元素a b c。那么当d要入队的时候,我们维护队列的上凸性质,即如果g[d,c]<g[c,b],那么就将c点删除。直到找到g[d,x]>=g[x,y]为止,并将d点加入在该位置中。

**3,求解时候,从队头开始,如果已有元素a b c,当i点要求解时,如果g[b,a]<sum[i],那么说明b点比a点更优,a点可以排除,于是a出队。最后dp[i]=getDp(q[head])。**

代码:

/* ***********************************************
Author :111qqz
Created Time :Sat 24 Sep 2016 02:16:33 PM CST
File Name :code/hdu/3507.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E5+7;
int a[N],sum[N];
int dp[N];
int n,m;
int q[N];
int head,tail;
int calDp( int i,int j)
{
    return dp[j] + m + ( sum[i] - sum[j] ) * ( sum[i] - sum[j] );
}
int calUp(int j,int k)
{
    return dp[j] + sum[j] * sum[j] - (dp[k] + sum[k] * sum[k]);
}
int calDown(int j,int k)
{
    return 2*(sum[j] - sum[k]);
}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    while (~scanf("%d%d",&n,&m))
    {
        sum[0] =  0;
        for  ( int i = 1  ; i <= n ; i++) scanf("%d",a+i),sum[i] = sum[i-1] + a[i];
        dp[0] = 0 ;
        head = tail = 0 ;
        q[tail++] =  0;
        for ( int i = 1 ; i <= n ; i++)
        {
        while (head+1<tail && calUp(q[head+1],q[head])<=sum[i]*calDown(q[head+1],q[head])) head++;
        dp[i] = calDp(i,q[head]);
        while (head+1<tail && calUp(i,q[tail-1])*calDown(q[tail-1],q[tail-2])<=calUp(q[tail-1],q[tail-2])*calDown(i,q[tail-1])) tail--;
        q[tail++] = i ;
        }
        printf("%d\n",dp[n]);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付