P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.
第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
输出最小费用
题目大意：给n个玩具，每个玩具有权值C[i]，分成几组，每组的值=组内玩具的权值之和+∑C[i]以及组内玩具个数-1，每组的代价=（每组的值-L）^2 ，问最优分组后的代价之和（即各组代价相加）
分析：首先，很快想到一个O(n^2)的做法，即Dp[i]表示前 i 个分组后的最小代价和，每次枚举一个 j，表示第 j+1 到 i 个分成一组，
转移为 DP[i] = MIN(DP[j]+( C[j+1]+C[j+2]+....+C[i]+i-j-1-L)^2 )，0 <= j < i
若设 Sum[i] = C[1]+C[2]+....C[i]
则转移为 DP[i] = MIN(DP[j]+ ( Sum[i]-Sum[j]+i-j-1-L)^2 )，0 <= j < i
再设 S[i] = Sum[i]+i
则转移为 DP[i] = MIN(DP[j]+ (S[i]-S[j]-1-L)^2 )，0 <= j < i
那么，对这个方程进行探究:
对于两个决策点k，j（k > j）
若选择在k+1....i 分组优于在 j+1...i 分组（即决策点k优于决策点 j ），则有
Dp[k]+(S[i]-S[k]-1-L)^2 < Dp[j]+(S[i]-S[j]-1-L)^2
-> Dp[k] + (S[i]-1-L)^2 + S[k]^2 - 2*(S[i]-1-L)*S[k] < Dp[j] + (S[i]-1-L)^2 + S[j]^2 - 2*(S[i]-1-L)*S[j]
-> (Dp[k]+S[k]^2) - (Dp[j]+s[j]^2) < 2*(S[i]-1-L)*(S[k]-S[j])
-> [ (Dp[k]+S[k]^2) - (Dp[j]+s[j]^2) ] / (S[k]-S[j]) < 2*(S[i]-1-L)
-> 即点（S[k], Dp[k]+S[k]^2）与点（S[j]，Dp[j]+s[j]^2 ）的斜率 < 2*(S[i]-1-L)
也就是说，若决策点k优于决策点j则必定有上式成立
显然对于固定的两点 j、k ，（S[i]-1-L）的值是递增的（因为 i 是递增的），
所以 对于任意的j、k都有这样情况，若当 i = x时，有决策点k优于决策点j，那么当 i = x+1, i = x+2, ......, i = n时，都有决策点k优于决策点j
所以我们可以维护一个单调递增的决策点队列x1,x2,x3,.....xn，并使得它们相邻点之间的斜率递增，
这样，随着（s[i]-1-L）的增加，不断维护队列中的点（即不断删除队头即可，因斜率递增）
每次算完Dp[i]后，显然我们要将 i 也作为决策点加入队列，在加入前，我们需考虑一点东西
假设队尾前一个为x，队尾为y，
若x、y的斜率大于y，i 的斜率，那么显然，决策点绝不可能是y（因为如果有x、y的斜率小于2*（S[i]-1-L），则必有y，i的斜率小于2*（s[i]-1-L）），并且如果保留y，还会影响决策（因为在维护队列的过程中，只看队头，要保持单调递增），所以要删去 y，
在不断的删去不合格的队尾后，再将决策点 i 加入
综上所述，本题得解
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <deque> 6 #include <vector> 7 #include <queue> 8 #include <iostream> 9 #include <algorithm> 10 #include <map> 11 #include <set> 12 #include <ctime> 13 using namespace std; 14 typedef long long LL; 15 typedef double DB; 16 #define For(i, s, t) for(int i = (s); i <= (t); i++) 17 #define Ford(i, s, t) for(int i = (s); i >= (t); i--) 18 #define MIT (2147483647) 19 #define INF (1000000001) 20 #define MLL (1000000000000000001LL) 21 #define sz(x) ((int) (x).size()) 22 #define clr(x, y) memset(x, y, sizeof(x)) 23 #define puf push_front 24 #define pub push_back 25 #define pof pop_front 26 #define pob pop_back 27 #define ft first 28 #define sd second 29 #define mk make_pair 30 inline void SetIO(string Name) { 31 string Input = Name+".in", 32 Output = Name+".out"; 33 freopen(Input.c_str(), "r", stdin), 34 freopen(Output.c_str(), "w", stdout); 35 } 36 37 const int N = 50010; 38 int n; 39 LL L; 40 LL C[N], Sum[N], S[N], Dp[N]; 41 int Que[N], Head, Tail; 42 43 inline LL Getint() { 44 char Ch = ‘ ‘; 45 LL Ret = 0; 46 while(!(Ch >= ‘0‘ && Ch <= ‘9‘)) Ch = getchar(); 47 while(Ch >= ‘0‘ && Ch <= ‘9‘) { 48 Ret = Ret*10LL+Ch-‘0‘; 49 Ch = getchar(); 50 } 51 return Ret; 52 } 53 54 inline void Input() { 55 scanf("%d", &n); 56 L = Getint(); 57 For(i, 1, n) C[i] = Getint(); 58 } 59 60 inline LL Sqr(LL x) { 61 return x*x; 62 } 63 64 inline bool Better(int x, int y, int i) { 65 return Dp[x]+Sqr(S[x])-Dp[y]-Sqr(S[y]) 66 <= 2LL*(S[i]-L-1)*(S[x]-S[y]); 67 } 68 69 inline bool Smaller(int x, int y, int z) { 70 LL DX1 = S[y]-S[x], DX2 = S[z]-S[y], 71 DY1 = Dp[y]+Sqr(S[y])-Dp[x]-Sqr(S[x]), 72 DY2 = Dp[z]+Sqr(S[z])-Dp[y]-Sqr(S[y]); 73 return DY1*DX2 <= DY2*DX1; 74 } 75 76 inline void Solve() { 77 For(i, 1, n) Sum[i] = Sum[i-1]+C[i]; 78 For(i, 1, n) S[i] = Sum[i]+i; 79 80 Head = Tail = 1, Que[1] = 0; 81 For(i, 1, n) { 82 int x, y; 83 while(Head < Tail) { 84 x = Que[Head], y = Que[Head+1]; 85 if(Better(x, y, i)) break; 86 Head++; 87 } 88 89 x = Que[Head]; 90 Dp[i] = Dp[x]+Sqr(S[i]-S[x]-1-L); 91 92 while(Head < Tail) { 93 x = Que[Tail-1], y = Que[Tail]; 94 if(Smaller(x, y, i)) break; 95 Tail--; 96 } 97 Que[++Tail] = i; 98 } 99 100 cout<<Dp[n]<<endl; 101 } 102 103 int main() { 104 SetIO("1010"); 105 Input(); 106 Solve(); 107 return 0; 108 }
原文：http://www.cnblogs.com/StupidBoy/p/4592581.html
