韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C×（韩i与韩i+1的高度差（1≤i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i，增高Hcm的花费是H2.请你帮助韩父让韩家损失最小。
Input
有若干组数据，一直处理到文件结束。
每组数据第一行为两个整数：韩子数量N(1≤N≤50000)和舟子系数C(1≤C≤100)
接下来N行分别是韩i的高度(1≤hi≤100)。
Output
对每组测试数据用一行输出韩家的最小损失。
Sample input and output
| Sample Input | Sample Output |
|---|---|
5 2 |
15 |
解题报告
用单调队列来优化（正解）...空间复杂度也可以优化到O(100*2)...好吧我又没有优化
当时先用的线段树来O(log)得到最优解，结果本机测试跑极限数据1.5s+才出。。。果断放弃(常数太大）
之后采用rmq...交了一发TLE，彻底断了我的念头...
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 5e4 + ;
int n,c,h[maxn];
ll q[];
ll f[maxn][];
ll MAX; int main(int argc,char *argv[])
{
MAX = << ;
MAX *= MAX;
while(scanf("%d%d",&n,&c) != EOF)
{
for(int i = ; i <= n ; ++ i)
scanf("%d",h+i);
for(int i = ; i <= n ; ++ i)
for(int j = ; j <= ; ++ j)
f[i][j] = MAX;
for(int i = h[] ; i <= ; ++ i)
f[][i] = (i-h[])*(i-h[]);
int front , rear ;
for(int i = ; i <= n ; ++ i)
{
front = rear = ;
for(int j = h[i-] ; j <= ; ++ j)
{
while(front < rear && f[i-][q[rear-]]-c*q[rear-] > f[i-][j]-c*j)
rear--;
q[rear++] = j;
}
for(int j = h[i] ; j <= ; ++ j)
if (j >= q[front])
f[i][j] = f[i-][q[front]] - c*q[front] + c*j + (j-h[i])*(j-h[i]);
front = rear = ;
for(int j = h[i-] ; j <= ; ++ j)
{
while(front < rear && f[i-][q[rear-]]+c*q[rear-] > f[i-][j]+c*j )
rear--;
q[rear++] = j;
}
for(int j = h[i] ; j <= ; ++ j)
{
while(j > q[front] && front < rear)
front++;
if (q[front] >= j)
f[i][j] = min(f[i][j],f[i-][q[front]] + c*q[front] - c*j + (j-h[i])*(j-h[i]));
}
}
ll ans = f[n][h[n]];
for(int j = h[n] ; j <= ; ++ j)
ans = min(ans,f[n][j]);
printf("%lld\n",ans);
}
return ;
}