[BZOJ1911]&&[Apio2010] 特别行动队

2014-12-02
竞赛题解 / 动态规划
APIOBZOJ

描述 Description

你有一支由 n 名预备役士兵组成的部队，士兵从 1 到 n 编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 (i, i + 1, …, i + k) 的序列。  编号为 i 的士兵的初始战斗力为 xi ，一支特别行动队的初始战斗力 x 为队内士兵初始战斗力之和，即 x = xi + xi+1 + … + xi+k。  通过长期的观察，你总结出一支特别行动队的初始战斗力 x 将按如下经验公式修正为 x’：x’ = ax2 + bx + c，其中 a, b, c 是已知的系数（a < 0）。  作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。  例如，你有 4 名士兵，x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1, b = 10, c = –20。此时，最佳方案是将士兵组成 3 个特别行动队：第一队包含士兵 1 和士兵 2，第二队包含士兵 3，第三队包含士兵 4。特别行动队的初始战斗力分别为 4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。

输入格式 InputFormat

输入由三行组成。第一行包含一个整数 n，表示士兵的总数。第二行包含三个整数 a, b, c，经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1, x2, …, xn，分别表示编号为 1, 2, …, n 的士兵的初始战斗力。

输出格式 OutputFormat

输出一个整数，表示所有特别行动队修正后战斗力之和的最大值。

样例输入 SampleInput

500
-1 100 -1000
12 58 12 11 22 59 41 54 5 16 87 74 88 55 21 50 16 79 94 10 96 90 22 12 60 6 78 96 59 8 52 3 51 63 59 96 90 56 57 25 38 62 89 47 12 77 3 14 62 75 65 76 66 18 29 4 54 62 41 47 22 50 73 30 43 58 91 69 33 68 59 23 82 79 94 34 12 63 17 81 49 7 10 13 51 91 86 44 31 82 59 92 73 30 31 23 48 54 97 89 21 69 4 74 26 95 47 82 1 1 92 55 22 72 92 50 25 66 21 76 83 60 76 30 16 63 41 90 58 66 57 48 8 28 24 46 25 70 55 67 73 98 96 50 88 37 71 6 86 15 35 24 95 25 25 17 72 84 60 24 65 47 2 99 28 60 86 17 98 35 79 62 5 16 40 32 18 8 92 65 40 1 36 25 53 45 98 5 39 44 52 56 25 85 29 21 35 39 71 45 31 96 7 66 58 65 41 4 90 55 63 3 17 6 3 58 74 56 10 43 70 52 88 66 26 71 18 22 28 55 31 33 7 87 14 8 70 82 90 19 71 91 75 61 24 28 60 48 78 97 98 38 66 68 44 79 25 3 12 7 22 17 89 94 78 17 100 42 35 19 20 72 1 60 85 7 17 24 5 97 14 14 94 26 38 4 42 26 40 7 7 70 83 25 13 55 92 66 27 86 91 16 2 3 16 46 32 99 67 34 39 55 28 17 80 40 85 28 39 24 57 56 60 74 90 95 44 84 96 13 40 19 28 64 17 33 84 100 53 63 32 50 41 46 38 23 7 71 89 91 38 95 94 50 83 72 75 31 98 29 41 76 14 82 81 13 53 56 5 48 39 50 15 87 61 40 54 84 37 43 41 66 44 9 69 33 11 78 46 20 26 19 68 9 10 42 6 57 69 51 47 12 3 73 68 11 91 87 90 55 99 68 88 13 72 81 96 13 41 71 67 76 61 57 58 69 51 31 34 85 34 67 74 89 53 6 28 8 32 47 88 30 40 27 24 76 12 68 25 5 20 56 46 93 38 60 87 16 79 38 87 68 91 38 86 43 84 52 9 83 24 58 94 67 1 23 88 55 92 9 71 90 93 99 8 87 34 86 99 13 98 50 64 32 89 71 12 9 17 8

样例输出 SampleOutput

362631

BZOJ 1911

斜率优化 DP。

原始方程：

\[ f[i]=Max \lbrace f[j]+a*(\sum_{k=j+1}^{i}x_{k})^{2}+b*\sum_{k=j+1}^{i}x_{k}+c \rbrace \]

化简前缀和得：

\[ f[i]=Max \lbrace f[j]+a*(sum[i]-sum[j])^{2}+b*(sum[i]-sum[j])+c \rbrace \]

设 \(k<j<i\) 且对于 \(i\) 而言 \(f[j]\) 优于 \(f[k]\)，则

\[ f[j]+a*(sum[i]-sum[j])^{2}+b*(sum[i]-sum[j])+c \\\\ >f[k]+a*(sum[i]-sum[k])^{2}+b*(sum[i]-sum[k])+c \]

整理得：

\[ \frac{(f[j]+a*sum[j]^{2}-b*sum[j])-(f[k]+a*sum[k]^{2}-b*sum[k])} {sum[j]-sum[k]}>2*a*sum[i] \]

于是用斜率优化来搞就好了。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll maxn=1000005;
ll i,j,t,n,m,l,r,k,z,y;
ll a,b,c;
ll x[maxn],sum[maxn],f[maxn],q[maxn];
ll head,tail;
inline ll fracup(ll x,ll y)
{
    return (f[x]+a*sum[x]*sum[x]-b*sum[x])-(f[y]+a*sum[y]*sum[y]-b*sum[y]);
}
inline ll fracdown(ll x,ll y)
{
    return sum[x]-sum[y];
}
int main()
{
    scanf("%lld",&n);
    scanf("%lld%lld%lld",&a,&b,&c);
    sum[0]=0;
    for (i=1;i<=n;i++) scanf("%lld",&x[i]),sum[i]=sum[i-1]+x[i];
    f[q[head=tail=0]]=0;
    for (i=1;i<=n;i++)
    {
        while (tail>head && fracup(q[head+1],q[head])>2*a*sum[i]*fracdown(q[head+1],q[head])) head++;
        t=q[head];m=sum[i]-sum[t];
        f[i]=f[t]+a*m*m+b*m+c;
        while (tail>head && fracup(q[tail],q[tail-1])*fracdown(i,q[tail])<fracup(i,q[tail])*fracdown(q[tail],q[tail-1])) tail--;
        q[++tail]=i;
    }
    printf("%lld\n",f[n]);
    return 0;
}