决策单调性优化 dp 简要笔记

引用 / 参考:绍兴一中相关课件,Acfboy 的博客

决策单调性

决策单调性指的是 dp 的决策时的最优位置是单调的。

常见地,若存在: dpi=f(dpj) 中,i 的决策位置是 posi,那么对于所有 i2,posiposi1

难点在于观察 (猜) 出其为决策单调,经常可以不证明。一般通过打表观察。

通用的决策单调性分治:

solve(l,r,L,R): l,r 表示区间范围, L,R 表示决策范围
if(l>r) exit
mid = (l+r) / 2
pos = query[L,R,mid] 从 L 到 R 中选取 mid 的最优决策
f[mid] = g(pos)
solve(l,mid-1,L,pos)
solve(mid+1,r,pos,R)

例题

Luogu3648 [APIO2014] 序列分割

省略推导过程,有:fi,k=maxfj,k1+(sisj)×sj,然后发现决策满足单调性,套上文的通用模板。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s[N],f[N][205],pre[N][205];
inline void solve(int l,int r,int L,int R,int k){
if(l>r) return;
int mid=(l+r)>>1;
int pos=0,maxx=0;
for(int i=L;i<=R;i++){
int t=f[i][k-1]+(s[mid]-s[i])*s[i];
if(t>maxx){
maxx=t;
pos=i;
}
}
f[mid][k]=maxx;pre[mid][k]=pos;
solve(l,mid-1,L,pos,k);solve(mid+1,r,pos,R,k);
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&s[i]);
s[i]+=s[i-1];
}
for(int i=1;i<=m;i++) solve(1,n,1,n,i);
printf("%lld\n",f[n][m]);
for(int x=n,i=m;i>=1;i--){
x=pre[x][i];
printf("%lld ",x);
}
return 0;
}

比斜率优化多一只 log,但是能卡过去。

本文作者:water_tomato

评论

  1. 2021-7-23
    2021-7-23 18:25:09

    受宠若惊

    • 博主
      Acfboy
      2021-7-23
      2021-7-23 18:28:43

      神仙 acfboy 博文写得太好了!

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇