这是一道动态规划的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
优化的对象就是f[k]。
通过例题来加深感受
http://www.acm.uestc.edu.cn/problem.php?pid=1685
我要长高
Description
韩父有N个儿子，分别是韩一，韩二…韩N。由于韩家演技功底深厚，加上他们间的密切配合，演出获得了巨大成功，票房甚至高达2000万。舟子是名很有威望的公知，可是他表面上两袖清风实则内心阴暗，看到韩家红红火火，嫉妒心遂起，便发微薄调侃韩二们站成一列时身高参差不齐。由于舟子的影响力，随口一句便会造成韩家的巨大损失，具体亏损是这样计算的，韩一，韩二…韩N站成一排，损失即为C*（韩i与韩i+1的高度差（1<=i
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]。转化成这样的形式，我们就可以用单调队列进行优化了。
第二个方程同理。
接下来便是如何实现，实现起来有点技巧。具体见下
1 #include
2 #include<string>
3 #include
4 #include
5 using namespace std;
6 #define inf 0xfffffff
7 #define min(a,b) a 8 #define max(a,b) a>b?a:b
9
10 int dp[2][101];
11 int n,c;
12 int q[101];
13 int head,tail,cur;
14
15 int main()
16 {
17 int i,j,x,nowf;
18 freopen("D:\\in.txt","r",stdin);
19 while(scanf("%d%d",&n,&c)==2)
20 {
21 scanf("%d",&x);
22 cur=0;
23 for(i=0;i)
24 dp[cur][i]=inf;
25 for(i=x;i<=100;i++)
26 dp[cur][i]=(x-i)*(x-i);
27 for(i=1;i)
28 {
29 scanf("%d",&x);
30 cur=1-cur;
31 //比前一个人高
32 head=tail=0;
33 for(j=0;j<=100;j++) //当身高为j时候，队列里便已经保存了0~j-1的信息，注意，是第i-1个人的信息
34 {
35 nowf=dp[1-cur][j]-j*c;
36 while(head1]>nowf)
37 tail--;
38 q[tail++]=nowf;
39 if(j<x)
40 dp[cur][j]=inf;
41 else
42 dp[cur][j]=q[head]+j*c+(x-j)*(x-j);
43 }
44 //比前一个人矮
45 head=tail=0;
46 for(j=100;j>=0;j--) //当身高为j时候，队列里便已经保存了100~j+1的信息，正写反写是有技巧的
47 {
48 nowf=dp[1-cur][j]+j*c;
49 while(head1]>nowf)
50 tail--;
51 q[tail++]=nowf;
52 if(j>=x)
53 dp[cur][j]=min(dp[cur][j],q[head]-j*c+(x-j)*(x-j));
54 }
55 }
56 int ans=inf;
57 for(i=0;i<=100;i++)
58 ans=min(ans,dp[cur][i]);
59 printf("%d\n",ans);
60 }
61 return 0;
62 }
具体代码有点困难，不理解的可以留言追问。
下面是我重写的代码感触颇多
#include
#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;itemp)rear--;que[rear++]=temp;if(j=0;j--){temp = dp[1-flag][j]+j*c;//记录如果前面的人比他高的情况此时就是在计算f[i-1][k] (k<=j)while(fronttemp)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
#include
#include
#include
#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;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
