hdu3507 Print Article DP+斜率优化

题意：就是给一个序列，让你分成很多段，每段按照题目的公式算出答案，要所有的答案加起来最小

思路一：（参考）http://www.cnblogs.com/lidaxin/p/5116577.html

斜率优化。
设f[i]表示前i个数分段后的最小值,则转移式为f[i]=min{f[j]+(sum[i]-sum[j])^2+M}，1<=j<i
进一步得:f[i]=min{ (f[j]+sum[j]^2-2*sum[i]*sum[j])+(sum[i]^2+M) }

设y(j)=f[j]+sum[j]^2，a[i]=sum[i]，x(j)=sum(j)，则f[i]=min{y(j)-2*a[i]*x(j)}+sum[i]^2+M

则要求min p=y+2ax , 单调队列维护下凸包。

while(L<R && q[L+1].y-2*sum[i]*q[L+1].x <= q[L].y-2*sum[i]*q[L].x) L++;
now.x = sum[i];
now.y = q[L].y-2*sum[i]*q[L].x+2*sum[i]*sum[i]+m;
while(L<R && cross(q[R-1],q[R],now)<=0) R--;
q[++R] = now;

now.y = y[i] = f[i]+sum[j]^2 = min{ (f[j]+sum[j]^2-2*sum[i]*sum[j])+(sum[i]^2+M) } + sum[i]^2

答案就是 y[n]=q[R].y=f[n]+sum[n]^2 ==> q[R].y-sum[n]^2；

代码一：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define mp(x,y) make_pair(x,y)
const int maxn = 5e5+10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
int n,m,a;
int sum[maxn];

struct node{
	int x,y;
}now,q[maxn];

int cross(node A,node B,node sum){
	return (B.x-A.x)*(sum.y-A.y) - (sum.x-A.x)*(B.y-A.y);
}

int main(){
	while(scanf("%d%d",&n,&m)==2){
		mem(sum);
		for(int i=1; i<=n; i++){
			scanf("%d",&a);
			sum[i] = sum[i-1]+a;
		}

		int L=0,R=0;
		for(int i=1; i<=n; i++){
			while(L<R && q[L+1].y-2*sum[i]*q[L+1].x <= q[L].y-2*sum[i]*q[L].x) L++;
			now.x = sum[i];
			now.y = q[L].y-2*sum[i]*q[L].x+2*sum[i]*sum[i]+m;
			while(L<R && cross(q[R-1],q[R],now)<=0) R--;
			q[++R] = now;
		}

		printf("%d\n",q[R].y-sum[n]*sum[n]);
	}

    return 0;
}

思路二：参考：http://www.cnblogs.com/kuangbin/archive/2012/08/26/2657650.html

kuangbin大神= = 非常详细

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define mp(x,y) make_pair(x,y)
const int maxn = 5e5+10;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////

int n,m;
int sum[maxn],f[maxn],q[maxn];

// int slope(int j,int k){ // WA!!! 
// 	return ((double)(f[j]+sum[j]*sum[j]-(f[k]+sum[k]*sum[k]))) / ((double)(2*(sum[j]-sum[k])));
// }

int getUP(int j,int k)
{
    return f[j]+sum[j]*sum[j]-(f[k]+sum[k]*sum[k]);
}
int getDOWN(int j,int  k)
{
    return 2*(sum[j]-sum[k]);
}

int main(){
	//f[i]=min((sum[i]-sum[j])^2+m+f[j])
	while(scanf("%d%d",&n,&m)==2){
		sum[0],f[0]=0;q[0]=0;
		for(int i=1; i<=n; i++){
			int a; scanf("%d",&a);
			sum[i] = sum[i-1]+a;
		}

		int L=0,R=0;
		for(int i=1; i<=n; i++){
			while(L<R && getUP(q[L+1],q[L]) <= sum[i]*getDOWN(q[L+1],q[L])) 
				L++;
			int j = q[L];
			f[i] = f[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + m;
			while(L<R && (getUP(i,q[R])*getDOWN(q[R],q[R-1]) <= getUP(q[R],q[R-1])*getDOWN(i,q[R]))) 
				R--;
			q[++R] = i;
		}

		// int L=0,R=0;
		// for(int i=1; i<=n; i++){
		// 	while(L<R && slope(q[L+1],q[L]) <= sum[i]) L++;
		// 	int j = q[L];
		// 	f[i] = f[j] + (sum[i]-sum[j])*(sum[i]-sum[j]) + m;
		// 	while(L<R && slope(i,q[R]) <= slope(q[R],q[R-1])) R--;
		// 	q[++R] = i;
		// }
		printf("%d\n",f[n]);
	}

    return 0;
}

秒客网

hdu3507 Print Article DP+斜率优化

相关文章