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
23514Sample Output
15
这题算是一个红果果的动态规划题了，但是很明显普通的做法是一个O(n^3)的算法，所以需要对这个动态规划过程进行单调队列优化。这里其实也就保留一个值就够了。详见代码：
#include#include #include #include #define INF 0x3fffffff#define MAXN 50005using 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; }