洛谷P3195 [HNOI2008]玩具装箱TOY
DP
题解
OI
经典的一道斜率优化DP,很久以前写的,现在再拿出来复习一下
简单读题可以得出本题的DP方程是
但是这样转移的复杂度高达,5e4的数据不能接受,需要优化.
为了简便计算,令.
假设存在决策和(),使得比更优,则有
展开式子得
移项
把变量除过去
为了看得更清楚,再令
经过这样的变换,这个DP方程就有了个斜率样子了:如果把看做纵坐标,把看做横坐标,那么就是过这两点的直线的斜率.
再重申一遍,只要满足上面这个式子(考虑每一个i时,左侧是一个常量!),决策k就比决策j更优.
由于是单调递增的,所以如果我们把对应的点依次绘制在坐标系上,就会构成一个函数(随便想一个函数的图像).每当我们将一个点从右侧连接到这个图像上是,就可以知道它与上一个点之间的斜率,再比较上上个点与上一个点的斜率,如果这两个斜率是递减的,说明当前决策一定更有可能比上一个决策最优!
这像不像一个单调队列?我们已经有了进队的条件了,可以维护一个优秀程度递增(在j递增的基础上)的单调队列了.
那么出队呢?很好的是,也是单调递增的.所以我们只要把当前看起来不会更优的点(队首斜率大于时)出队,让当前可以更优的点成为队首.
所以像这样能用单调队列解决的关键点:
- 能把两个决策点优劣的关系式化成斜率式
- 式子左边对i具有单调性
- 式子右边视作x坐标的项对j具有单调性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
const int MAXN = 50050;
int64 a[MAXN];
int64 n,L;
int64 sum[MAXN],s[MAXN],h[MAXN];
int64 que[MAXN];
int64 dp[MAXN];
double cal(int j,int k){
return (double)(dp[k]-dp[j] + h[k]-h[j])/(s[k] - s[j]);
}
int main(){
cin >> n >> L;
for(int i = 1;i<=n;i++){
cin >> a[i];
sum[i] = sum[i-1] + a[i];
s[i] = sum[i] + i;
h[i] = (s[i]+L+1) * (s[i]+L+1);
}
h[0] = (L+1) * (L+1);
int head = 0,tail = 0;
for(int i = 1;i<=n;i++){
while(head < tail && cal(que[head],que[head+1]) <= 2*s[i]){
head++;
}
dp[i] = dp[que[head]] + (s[i]-s[que[head]]-L-1)*(s[i]-s[que[head]]-L-1);
while(head < tail && cal(que[tail],i) < cal(que[tail-1],que[tail])){
tail--;
}
que[++tail] = i;
}
cout << dp[n] << endl;
}
|
