UESTC我要长高 DP优化

Description

韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i+1的高度差（1<=i<N））之和，搞不好连女儿都赔了.韩父苦苦思索，决定给韩子们内增高（注意韩子们变矮是不科学的只能增高或什么也不做），增高1cm是很容易的，可是增高10cm花费就很大了，对任意韩i，增高Hcm的花费是H^2.请你帮助韩父让韩家损失最小。

Input

有若干组数据，一直处理到文件结束。
每组数据第一行为两个整数：韩子数量N(1<=N<=50000)和舟子系数C(1<=C<=100)
接下来N行分别是韩i的高度(1<=hi<=100)。

Output

对每组测试数据用一行输出韩家的最小损失。

Sample Input

5 2
2
3
5
1
4

Sample Output

这题算是一个红果果的动态规划题了，但是很明显普通的做法是一个O(n^3)的算法，所以需要对这个动态规划过程进行单调队列优化。这里其实也就保留一个值就够了。详见代码：

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3fffffff
#define MAXN 50005
using namespace std;

int N, M, H[MAXN], dp[MAXN][105];
// dp[i][j] 第i个人身高为j时的最少代价
// 当前面的身高小于其身高时 
// dp[i][j] = min( dp[i-1][k] + Mj - Mk + (j - H[i])^2 )同理
// 对于上面的式子我们只需要维护好上一次状态的 dp[i-1][k]-Mk 的最小值就可以了
// dp[i][j] = min( dp[i-1][k] + Mk - Mj + (j - H[i])^2 );
// 对于上面的式子我们只需要维护好上一次状态的 dp[i-1][k]+Mk 的最小值就可以了

int main()
{
    int LIM, Min;
    while (scanf("%d %d", &N, &M) == 2) {
        LIM = -INF;
        for (int i = 1; i <= N; ++i) {
            scanf("%d", &H[i]);
            LIM = max(LIM, H[i]); // 最优解一定不会超过最高的一个人的高度 
        } 
        for (int i = 0; i <= N; ++i) {
            memset(dp[i], 0x3f, sizeof (dp[i]));    
        } 
        for (int i = H[1]; i <= LIM; ++i) {  // i < H[i] 的状态的无意义的，因为身高不可变低 
            dp[1][i] = (i - H[1]) * (i - H[1]); 
        } 
        for (int i = 2; i <= N; ++i) {  // i 号已经提前进行了初始化，从2号开始
            Min = INF;  // 保留上一层的最小值
            for (int j = H[i-1]; j <= LIM; ++j) {
                Min = min(Min, dp[i-1][j] - M*j); 
                if (j >= H[i]) { 
                    dp[i][j] = Min + M*j + (j - H[i]) * (j - H[i]);
                } 
            }
            Min = INF;
            for (int j = LIM; j >= H[i]; --j) {
                Min = min(Min, dp[i-1][j] + M*j);
                if (j >= H[i]) {
                    dp[i][j] = min(dp[i][j], Min - M*j + (j - H[i]) * (j - H[i]));
                } 
            }
        }
        Min = INF;
        for (int i = H[N]; i <= LIM; ++i) {
            Min = min(Min, dp[N][i]);
        }
        printf("%d\n", Min);
    }
    return 0;    
}