BZOJ . 1010
题意：
这道题的意思就是说有n个数，分成连续的若干段，每段（假设从第j个到第i个组成一段）的分数为 (X-L)^2，X为j-i+Sigma(Ck) ，i<=k<=j，其中L是一个常量。目标：各段分数的总和最小。
题解：
首先这道题是一道dp题，我们设dp[ i ]表示从0 到 i 这一段的最小花费，再用一个sum[ i ]来记录一个前缀和，所以我们可以写出状态转移方程：
dp[ i ] = min( dp[ j ] + ( s[ i ] - s[ j ] + i - ( j + 1 ) - L ) ^ 2;
但是我们发现这样的话，我们要枚举i 从 1 到 n，枚举j 从 1 到 i，时间复杂度为O ( n ^2 ),而n的范围是50000，所以这样是肯定过不了的，所以程序需要优化。
我们假设存在这样的k，使得0<j<k<=i，利用四边形不等式有关知识，我们可以发现这道问题具有决策单调性，所以若存在一个k满足比j的方案更优，则j不会用来更新dp[ i ]，所以我们可以得到：
dp[ j ] + ( s[ i ] + s[ j ] + i - ( j + 1 ) - L ) ^ 2 >= dp[ k ] + ( s[ i ] + s[ k ] + i - ( k + 1 ) - L ) ^ 2
令s[ i ] + i = sum[ i ]， L + 1 = c;
经过整理我们得到：
dp[ k ] + ( sum[ k ] + c ) ^ 2 - (dp[ j ] + ( sum[ j ] + c ) ^ 2 ) <=2 * s[ i ] * ( s[ k ] - s[ j ] )
我们将 ( s[ k ] - s[ j ] ) * 2移到左边就可以得到一个类似于数学中斜率求法的东西，然后我们在通过这个不等式在一个队列中来维护一个下凸壳。
队列中存放有可能更新i的点，我们每次进队前先找到用哪一个点来更新当前的i，具体做法是判断s[ i ]和队头元素和队头后一个元素的斜率( 就是之前得到的不等式将( s[ k ] - s[ j ] ) * 2移到左边得到的式子 )，若s[ i ]小于当前斜率，那么用当前队头元素更新dp[ i ]，否则头指针指向下一元素，用更新之后的头指针来更新dp[ i ]，更新完dp[ i ]后，再来维护队尾，通过下凸壳来维护，这样优化之后就可以只需要跑一边每个点，就可以得到答案，时间复杂度降为O( n )，最后答案就是输出dp[ n ]。
代码：
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 500001; long long q[N],dp[N],s[N],n,l,c; long long sq(long long a){ return a * a; } long long omg(int a, int b){ return dp[b] + sq(s[b] + c) - dp[a] - sq(s[a] + c);//double可能由精度限制，所以能用整型就用整型 } int main(){ scanf("%lld%lld",&n,&l); for (int i = 1; i <= n; i++){ scanf("%lld",&s[i]); s[i] += s[i - 1]; } for (int i = 1; i <= n; i++) s[i] += i; c = l + 1; int head = 1, tail = 1; q[tail] = 0; for (int i = 1; i <= n; i++){ while (head != tail && omg(q[head],q[head + 1]) <= 2 * s[i] * (s[q[head + 1]] - s[q[head]])) head++；//先找到用哪一个元素更新当前dp[ i ]；int t = q[head]; dp[i] = dp[t] + sq(s[i] - s[t] - c);//更新dp[ i ]; while (head != tail && omg(q[tail],i) * 2 * (s[q[tail]] - s[q[tail - 1]]) < omg(q[tail - 1],q[tail]) * 2 * (s[i] - s[q[tail]])) tail--;//维护队尾 q[++tail] = i;//易错 ： 记得把当前元素进队 } printf("%lld ",dp[n]); return 0; }