洛谷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; }
|