BZOJ 1911: [Apio2010]特别行动队 （斜率优化DP）

BZOJ1911

1911: [Apio2010]特别行动队

Time Limit: 4 Sec Memory Limit: 64 MB Submit: 2695 Solved: 1209 [Submit][Status][Discuss]

Description

Input

Output

Sample Input

4 -1 10 -20 2 2 3 4

Sample Output

9

HINT

一道比较水的斜率优化的题目。 进行DP，然后把方程写出来就可以了。 mark下。

/* ***************

Author        :kuangbin

Created Time  :2015/5/5 21:49:21

File Name     :F:\ACM\2015ACM\专题练习\斜率DP\BZOJ1911.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 1000010;

long long sum[MAXN];

long long X[MAXN],Y[MAXN];

long long dp[MAXN];

long long det(int k,int j,int i){

	long long x1 = X[j] - X[k];

	long long y1 = Y[j] - Y[k];

	long long x2 = X[i] - X[k];

	long long y2 = Y[i] - Y[k];

	return x1*y2 - x2*y1;

}

int que[MAXN];

int main()

{

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

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

	int a,b,c;

	int n;

	while(scanf("%d",&n) == 1){

		scanf("%d%d%d",&a,&b,&c);

		sum[0] = 0;

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

			int tmp;

			scanf("%d",&tmp);

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

		}

		dp[0] = 0;

		X[0] = 0;

		Y[0] = 0;

		int st,ed;

		st = ed = 0;

		que[ed++] = 0;

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

			int k = 2*a*sum[i];

			while(st+1 < ed && Y[que[st]]-k*X[que[st]] <= Y[que[st+1]]-k*X[que[st+1]])st++;

			dp[i] = a*sum[i]*sum[i] + b*sum[i] + c + Y[que[st]] - k*X[que[st]];

			X[i] = sum[i];

			Y[i] = dp[i] + a*sum[i]*sum[i] - b*sum[i];

			while(st+1 < ed && det(que\[ed-2\],que\[ed-1\],i) >= 0)ed--;

			que[ed++] = i;

		}

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

	}

    

    return 0;

}