洛谷题目链接:[APIO2010]特别行动队

题目描述

你有一支由 n 名预备役士兵组成的部队，士兵从 1 到 $n$ 编号，要将他们拆分成若干特别行动队调入战场。出于默契的考虑，同一支特别行动队中队员的编号应该连续，即为形如 $(i, i + 1, ..., i + k)$ 的序列。编号为 $i$ 的士兵的初始战斗力为 $x_i$ ，一支特别行动队的初始战斗力 $x$ 为队内士兵初始战斗力之和，即 $x = x_i + x_{i+1} + ... + x_{i+k}$ 。

通过长期的观察，你总结出一支特别行动队的初始战斗力 $x$ 将按如下经验公式修正为 $x':x'= ax^2+bx+c$,其中 a, b, c 是已知的系数（a < 0）。作为部队统帅，现在你要为这支部队进行编队，使得所有特别行动队修正后战斗力之和最大。试求出这个最大和。

例如，你有 4 名士兵，$x_1 = 2, x_2 = 2, x_3 = 3, x_4 = 4$.经验公式中的参数为 a = –1, b = 10, c = –20。此时，最佳方案是将士兵组成 3 个特别行动队：第一队包含士兵 1 和士兵 2，第二队包含士兵 3，第三队包含士兵 4。特别行动队的初始战斗力分别为 4, 3, 4，修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9，没有其它方案能使修正后的战斗力和更大。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

4

-1 10 -20

2 2 3 4

输出样例#1：

说明

20%的数据中，n ≤ 1000；

50%的数据中，n ≤ 10,000；

100%的数据中，1 ≤ n ≤ 1,000,000，–5 ≤ a ≤ –1，|b| ≤ 10,000,000，|c| ≤ 10,000,000，1 ≤ xi ≤ 100

一句话题意: 将$n$个士兵分成若干组,设他们的战斗力之和为$x$,则新得到的战斗力为$x'$,$x'=a*x^2+b*x+c$,现在要求出一种方法使得总战斗力之和最大.

题解: DP方程应该很容易想到,设$f[i]$表示到第$i$个人所能得到的最大的战斗力.显然有$$f[i]=max(f[i], f[j]+a(pre[i]-pre[j])^2+b(pre[i]-pre[j])+c$$

其中$(0\leq j<i)$,$pre[i]$代表1~$i$个人的战斗力的前缀和.

那么显然如果直接用DP来做的话,时间复杂度是$O(n^2)$的.那么我们就需要想一下优化.接下来我们需要对这个DP方程进行化简,假设$j$状态为转移到$i$状态的最优解,则有:

\[f[i]=f[j]+a*(pre[i]-pre[j])^2+b*(pre[i]-pre[j])+c
\]

\[f[i] = f[j]+a*pre[i]^2-2*a*pre[i]*pre[j]+a*pre[j]^2+b*pre[i]-b*pre[j]+c
\]

移项成斜率式,则有$$22pre[i]pre[j]+f[i]-apre[i]^{2-b*pre[i]-c=a*pre[j]}2-b*pre[j]+f[j]$$

我们把$pre[j]$看做直线的$x$ , 将$2*a*pre[i]*pre[j]$看做直线的斜率,$a*pre[j]^2-b*pre[j]+f[j]$看做直线的$y$,将$f[i]-b*pre[i]-a*pre[i]^2-c$看做斜率的截距,既然题目维护的是最大值,那么就要维护一个上凸包(当然套路是一样的),之后的就直接套路搞就可以了.

#include<bits/stdc++.h>

using namespace std;

const int N=1000000+5;

typedef long long lol;

lol n, a, b, c, w[N], pre[N], h = 0, t = 0, q[N], f[N];

lol gi(){

	lol ans = 0, f = 1; char i = getchar();

	while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}

	while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}

	return ans * f;

}

lol calc(lol x){return a*x*x+b*x+c;}

lol X(lol i){return pre[i];}

lol Y(lol i){return f[i]+a*pre[i]*pre[i]-b*pre[i];}

double slope(lol i, lol j){return (double) (Y(i)-Y(j))/(X(i)-X(j));}

int main(){

	n = gi(), a = gi(), b = gi(), c = gi();

	for(int i=1;i<=n;i++) w[i] = gi(), pre[i] = pre[i-1]+w[i];

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

		while(h < t && slope(q[h], q[h+1]) > (double) 2.0*a*pre[i]) h++;

		f[i] = f[q[h]]+calc(pre[i]-pre[q[h]]);

		while(h < t && slope(q[t], q[t-1]) < slope(q[t], i)) t--;

		q[++t] = i;

	}

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

	return 0;

}

秒客网

[洛谷P3628] [APIO2010]特别行动队

洛谷题目链接:[APIO2010]特别行动队

题目描述

输入输出格式

输入输出样例

说明

相关文章