洛谷题目链接:
题目描述
你有一支由 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：
9
说明
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\] 移项成斜率式,则有\[2*2*pre[i]*pre[j]+f[i]-a*pre[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\)看做斜率的截距,既然题目维护的是最大值,那么就要维护一个上凸包(当然套路是一样的),之后的就直接套路搞就可以了.#includeusing 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;}