uestc oj 1685 我要长高

这是一道动态规划的dp问题

但是明显需要O（n^3）的时间复杂度  ，显然需要进行优化，

并且有明显的可以进行单调队列优化的特征，在本次确定高度之后，

总能在前一次当中寻找到一个最优解。

最优解当然是由上一次的积累量+本次积累量（其中上一次的积累量与本次的积累量之间无关联）

就是说dp[i-1][k]的积累量只是与k有关  dp[i][j]的积累量至于j有关

由本次状态转移方程

dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j))；其中x[i]是第i个儿子原本的身高

通过分解满足条件

下面摘抄一位大牛的博客

http://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html

单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解，ect。。。

 

单调队列可以有两个操作：

1、插入一个新的元素，该元素从队尾开始向队首进行搜索，找到合适的位置插入之，如果该位置原本有元素，则替换它。

2、在过程中从队首删除不符合当前要求的元素。

 

单调队列实现起来可简单，可复杂。简单的一个数组，一个head，一个tail指针就搞定。复杂的用双向链表实现。

 

用处：

1、保存最优解，次优解，ect。

2、利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。也就是说，将原本会超时的N维dp降优化至N-1维，以求通过。这也是我想记录的重点

是不是任何DP都可以利用单调队列进行优化呢？答案是否定的。

记住！只有形如 dp[i]=max/min (f[k]) + g[i]  （k<i && g[i]是与k无关的变量）才能用到单调队列进行优化。

优化的对象就是f[k]。

 

通过例题来加深感受

http://www.acm.uestc.edu.cn/problem.php?pid=1685

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　我要长高

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)。

 

首先建立方程，很容易想到的是，dp[i][j]表示第 i 个儿子身高为 j 的最低花费。分析题目很容易知道，当前儿子的身高花费只由前一个儿子影响。因此，

dp[i][j]=min(dp[i-1][k] + abs(j-k)*C + (x[i]-j)*(x[i]-j))；其中x[i]是第i个儿子原本的身高

我们分析一下复杂度。

首先有N个儿子，这需要一个循环。再者，每个儿子有0到100的身高，这也需要一维。再再者，0到100的每一个身高都可以有前一位儿子的身高0到100递推而来。

所以朴素算法的时间复杂度是O(n^3)。题目只给两秒，难以接受！

分析方程：

当第 i 个儿子的身高比第 i-1 个儿子的身高要高时，

dp[i][j]=min(dp[i-1][k] + j*C-k*C + X);   ( k<=j ) 其中 X=(x[i]-j)*(x[i]-j)。

当第 i 个儿子的身高比第 i-1 个儿子的身高要矮时，

dp[i][j]=min(dp[i-1][k] - j*C+k*C + X);   ( k>=j )

对第一个个方程，我们令 f[i-1][k]=dp[i-1][k]-k*C,  g[i][j]=j*C+X; 于是 dp[i][j] = min (f[i-1][k])+ g[i][j]。转化成这样的形式，我们就可以用单调队列进行优化了。

第二个方程同理。

接下来便是如何实现，实现起来有点技巧。具体见下

 

具体代码有点困难，不理解的可以留言追问。 

下面是我重写的代码感触颇多

#include<cstdio>
#define inf 0xfffffff
int n,c,flag,a,i,j,front,rear,temp;
int que[100];
int dp[2][110];//用于记录最优解只保存最后结果int main()
{freopen("1.txt","r",stdin);printf("%d\n",inf);while(scanf("%d%d",&n,&c)==2){flag = 0;scanf("%d",&a);for(i=0;i<a;i++)//低于自己的身高是没有意义的{dp[flag][i] = inf;}for(i=a;i<=100;i++){dp[flag][i] = (i-a)*(i-a);}for(i=1;i<n;i++){scanf("%d",&a);flag = 1-flag;front = 0;rear = 0;for(j=0;j<=100;j++)//如果前面的人比他矮的话{temp = dp[1-flag][j]-j*c;//此时就是在计算f[i-1][k] (k<=j)while(front<rear&&que[rear-1]>temp)rear--;que[rear++]=temp;if(j<a)dp[flag][j] = inf;elsedp[flag][j] = que[front]+j*c+(j-a)*(j-a);}front =0;rear = 0;for(j=100;j>=0;j--){temp = dp[1-flag][j]+j*c;//记录如果前面的人比他高的情况此时就是在计算f[i-1][k] (k<=j)while(front<rear&&que[rear-1]>temp)rear--;que[rear++] = temp;if(j>=a){if(dp[flag][j]>que[front]-j*c+(j-a)*(j-a))dp[flag][j] = que[front]-j*c+(j-a)*(j-a);}}}int ans = inf;for(i=0;i<=100;i++){if(ans>dp[flag][i])ans = dp[flag][i];}printf("%d\n",ans);}return 0;
}

首先是在inf的存取上来说，一开始把7个f看成了8个f造成了不理解，明明是取一个很大的值，怎么变成了一个-1呢？

随后自己取了0x7fffffff这个值，结果出现了错误，原因是在过程中会进行加法，这个最大的int整形，加上一个数字之后就变成了

负数了。于是就得出了十分错误的结果。

还有就是在起初初始化的时候对小于a的值进行inf赋值是很有必要性的，因为其实每个值都会用得上的，都会进行计算入队的

我们只是取得最小值（符合条件的）

下面这个解法是我从另一个博客摘取的 效率更高

其实我们根本没有必要去维护一个队列，其实只需要要在高于或者矮于的情况下的最小值就行了，于是乎在

队列维护的时候只是需要一次最小值比较就行了

还有在高于前一个人的情况下只是需要从H【i-1】开始枚举到MLen就行了

在矮于前一个人的身高的时候  只需要从Mlen 到 H【i】枚举就行了

很好吧

http://www.cnblogs.com/Lyush/archive/2012/08/17/2644676.html

#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;    
}