hdu 3507 Print Article (斜率优化dp)

题目链接

题意：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....

斜率优化登场！

这篇博客讲得非常好

我们假设k两边移项一下，得到：(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;
}