「单调优化 dp」做题记录

发布时间：2025-05-15 01:19

「单调优化 dp」做题记录

P1941 [NOIP2014 提高组] 飞扬的小鸟

设 f(i,j)" role="presentation">f(i,j) 表示使小鸟到达 (i,j)" role="presentation">(i,j) 所需的最少点击数。

不难写出转移方程：

f(i,j)=min{f(i−1,j+yi−1),ifj+yi−1≤mf(i−1,x−kxi−1),k∈N+∧j−kxi−1≥1" role="presentation">f(i,j)=min{f(i−1,j+yi−1),ifj+yi−1≤mf(i−1,x−kxi−1),k∈N+∧j−kxi−1≥1

其中第一种情况对应在上一点不点击，第二种情况对应在上一点点击若干次（k" role="presentation">k 次）。由于小鸟高度为 m" role="presentation">m 时，无法再上升，所以 j=m" role="presentation">j=m 的情况要特殊处理。

初始化：

f(i,j)={0,i=0+∞,Otherwise" role="presentation">f(i,j)={0,i=0+∞,Otherwise

如果 ∀1≤j≤m" role="presentation">∀1≤j≤m，f(n,m)=+∞" role="presentation">f(n,m)=+∞，则无法到达终点，否则到达终点的最小点击数为 min1≤j≤mf(n,j)" role="presentation">min1≤j≤mf(n,j)。

容易发现，由于要枚举 k" role="presentation">k，每次转移的时间复杂度大于 O(1)" role="presentation">O(1)。虽然在开启 O2 的情况下能通过此题，但我们仍需更好的转移方程。

但是我还没搞懂优化，洛谷题解写的都是什么东西？还有这不是单调优化题单里的题吗，我怎么没看出单调优化，题解里都在说完全背包的事剩下的转移方程，以后再来探索吧

P3089 [USACO13NOV] Pogo-Cow S

不失一般性，假设 Bessie 从左往右跳。并且先把所有目标点按坐标从小到大排序。

设 f(i,j)" role="presentation">f(i,j) 表示 Bessie 在由第 j" role="presentation">j 个目标点跳到第 i" role="presentation">i 个目标点的情况下，能获得的最大总分数。设 i" role="presentation">i 与 j" role="presentation">j 之间的距离 xi−xj=dis" role="presentation">xi−xj=dis，则转移方程为

f(i,j)=maxk<j∧xj−xk≤disf(k,j)+vali" role="presentation">f(i,j)=maxk<j∧xj−xk≤disf(k,j)+vali

初始化 ∀1≤i≤n,f(i,0)=vali" role="presentation">∀1≤i≤n,f(i,0)=vali，代表从第 i" role="presentation">i 个目标点开始跳跃；其他情况下 f(i,j)=−∞" role="presentation">f(i,j)=−∞。

答案为 maxf(i,j)" role="presentation">maxf(i,j)。

P2627 [USACO11OPEN] Mowing the Lawn G

设 f(i,1/0)" role="presentation">f(i,1/0) 表示在选/不选第 i" role="presentation">i 只奶牛的情况下，前 i" role="presentation">i 只奶牛能获得的最大总收益。

则转移方程为

f(i,1)=maxi−K+1≤j<i(∑k=jiEk+f(j−1,0))f(i,0)=max(f(i−1,0),f(i−1,1))" role="presentation">f(i,1)=maxi−K+1≤j<i(∑k=jiEk+f(j−1,0))f(i,0)=max(f(i−1,0),f(i−1,1))

时间复杂度为 O(NK)" role="presentation">O(NK)，无法通过此题。

由于 f(i,1)" role="presentation">f(i,1) 的转移方程中出现了某一连续段的最大值，考虑单调优化。

这里的单调优化略微有点说法： ∑k=jiEk" role="presentation">∑k=jiEk 这一项是随着 i" role="presentation">i 的变化而动态更新的，因此单调队列中不能对于每个 j" role="presentation">j 维护 ∑k=jiEk+f(j−1,0)" role="presentation">∑k=jiEk+f(j−1,0)。

利用前缀和：∑k=jiEk=sumi−sumj−1" role="presentation">∑k=jiEk=sumi−sumj−1，则原转移方程变为：

f(i,1)=maxi−K+1≤j<i(f(j−1,0)−sumj−1)+sumi" role="presentation">f(i,1)=maxi−K+1≤j<i(f(j−1,0)−sumj−1)+sumi

于是就可以在单调队列中维护 f(j−1,0)−sumj−1" role="presentation">f(j−1,0)−sumj−1。

AC 记录

P2254 [NOI2005] 瑰丽华尔兹

先想一个 O(NMT)" role="presentation">O(NMT) 的做法：设 f(t,i,j)" role="presentation">f(t,i,j) 表示 t" role="presentation">t 时刻在 (i,j)" role="presentation">(i,j) 的情况下，已经过的最长滑行距离。

则转移方程为：

f(t,i,j)=max(f(t−1,i,j),f(t−1,si,sj)+1)" role="presentation">f(t,i,j)=max(f(t−1,i,j),f(t−1,si,sj)+1)

其中 (si,sj)" role="presentation">(si,sj) 表示上一时刻钢琴的位置，这是由上一时刻的风向决定的。

初始化：若 (i,j)" role="presentation">(i,j) 是空地，则 f(1,i,j)=0" role="presentation">f(1,i,j)=0，否则 f(1,i,j)=−∞" role="presentation">f(1,i,j)=−∞。

提交记录（50 pts）

由于 T" role="presentation">T 最大可以达到 40000" role="presentation">40000，而时间复杂度中的 NM" role="presentation">NM 难以去掉，所以考虑去掉 T" role="presentation">T。

重新设计状态：设 f(x,i,j)" role="presentation">f(x,i,j) 表示第 x" role="presentation">x 个区间结束时（即在 tx+1" role="presentation">tx+1 时刻），钢琴在 (i,j)" role="presentation">(i,j) 的情况下，已经过的最长滑行距离。

则转移方程为：

f(x,i,j)=max0≤d≤tx−sx+1(f(x−1,si,sj)+d)" role="presentation">f(x,i,j)=max0≤d≤tx−sx+1(f(x−1,si,sj)+d)

这里，我们枚举 d" role="presentation">d 表示在第 x" role="presentation">x 个区间中钢琴滑行的距离，(si,sj)" role="presentation">(si,sj) 表示滑行前所在的位置。

由于转移方程中出现了某一连续段的最大值，我们可以使用单调优化。

由于 d" role="presentation">d 是变化量，我们把他拆开： d=j−sj" role="presentation">d=j−sj （这里以向左移动为例），把 j" role="presentation">j 提出来，sj" role="presentation">sj 就变成了常量，这样就可以单调优化。

这里代码实现上需要一些小技巧，否则会使代码很冗长。对于不同的移动方向，我们计算两个点距离的方式也不同。在代码中，可以把这个过程抽象成一个函数，用某个变量 i 表示当前格是所在行/列的第 i 个格，这样就可以完成不同方向的统一。详见代码（代码中使用了滚动数组）：

void work(int x, int y, int d, int len) {head = 1, rear = 0;for(int i = 1; check(x, y); i++, x += dx[d], y += dy[d]){if(mp[x][y] == 'x') head = 1, rear = 0;else{while(head <= rear && f[x][y]-i >= que[rear].val - que[rear].pos) rear--;que[++rear] = Node(f[x][y], i);while(head <= rear && que[head].pos < i - len) head++;f[x][y] = que[head].val + (i - que[head].pos);ans = max(ans, f[x][y]);}} }

主函数中：

memset(f, 0xc0, sizeof(f)); f[sx][sy] = 0; for(int k = 1, s, t, d; k <= K; k++) { cin >> s >> t >> d; int len = t - s + 1; if(d == 1) for(int i = 1; i <= m; i++) work(n, i, 1, len); else if(d == 2) for(int i = 1; i <= m; i++) work(1, i, 2, len); else if(d == 3) for(int i = 1; i <= n; i++) work(i, m, 3, len); else if(d == 4) for(int i = 1; i <= n; i++) work(i, 1, 4, len); }

AC 记录

P1725 琪露诺

设 f(i)" role="presentation">f(i) 表示到达第 i" role="presentation">i 格时琪露诺能获得的最大冰冻指数。

转移方程（省略 0≤j≤N" role="presentation">0≤j≤N 等边界条件）：

f(i)=maxi−R≤j≤i−Lf(j)+Ai" role="presentation">f(i)=maxi−R≤j≤i−Lf(j)+Ai

初始化：f(0)=0" role="presentation">f(0)=0，其他情况 f(i)=−∞" role="presentation">f(i)=−∞。

答案统计：ans=maxN+1≤i≤N+Rf(i)" role="presentation">ans=maxN+1≤i≤N+Rf(i)

很难不想到单调优化，很难不会实现单调优化。

「单调优化 dp」做题记录

__EOF__