写一些简单的 1D/1D 的决策单调性优化...
这种决策单调性优化的过程：列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分
我们以一些例题为例：
<h2>[ZROI普转提]Bead</h2>
注：该题有权限，看不到的就看下一题。
这一题我们推出朴素的状态转移方程：
设 $f[i][k]$ 表示前 $i$ 个数中分成 $k$ 段的最小价值，转移为 $ f[i][k] = min{f[j-1][k-1] + w[j][i]} $，其中 $w[i][j]$ 表示 $i$ 到 $j$ 的价值。
显然 $ w[i][j] $ 可以通过维护 $cnt$ 数组 $N^2$ 求。
我们打表发现 $w$ 是递增的，说明该方程具有决策单调性。
决策单调性有一种较为简单的类似于整体二分的做法就是目前计算 $f[l\cdots r]$ 并且已知它们的决策都在 $[L, R]$ 中，每次暴力计算 $ f[mid] $ 即可。
只需要全局开两个指针 $i,j$ 和一个数组在每次计算 $ f[mid] $ 的时候移动过去并且维护 $cnt$ 即可。
复杂度 $O(nklog_2n)$.
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define LL long long
#define U unsigned
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define RFOR(i,a,b) for(int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 100000 + 5;
const int MAXK = 20 + 5;
int N,K;
int a[MAXN];
int fMAXN,cnt[MAXN],t[MAXN];
int L,R,ans;
// fi = std::min(fi,fj-1 + wj);
inline int query(int l,int r){
while(L > l) ans += cnt[a[--L]]++;
while(R < r) ans += cnt[a[++R]]++;
while(L < l) ans -= --cnt[a[L++]];
while(R > r) ans -= --cnt[a[R--]];
return ans;
}
void work(int k,int l,int r,int pl,int pr){
if(l > r) return;
if(l == r){
FOR(i,pl,pr) fl = std::min(fl,fi-1 + query(i,l));
return;
}
int mid = (l + r) >> 1;
FOR(i,pl,pr)
t[i] = fi-1 + query(i,mid);
int next = 0;
FOR(i,pl,pr)
if(!next || t[i] < t[next])
next = i;
fmid = t[next];
work(k,l,mid-1,pl,next);
work(k,mid + 1,r,next,pr);
}
int main(){
scanf("%d%d",&N,&K);
FOR(i,1,N)
scanf("%d",a+i);
L = 1;R = 0;
memset(f,0x7f,sizeof(f));
f0 = 0;
FOR(i,1,K) work(i,1,N,1,N);
printf("%dn",fN);
return 0;
}
[NOI2009]诗人小G
这一题我们可以轻松的推出朴素的状态转移方程：
设 $f[i]$ 表示前 $ i $ 个句子的最小不协调度，那么 $ f[i] = min{f[j] + |sum[j]-sum[i-1]-L-1|^P} $
我们随意的打个表，发现后面的那一项是递增的。（其实我也不会证明 qaq）
也就是说：我们在转移的时候，不需要考虑较大的状态，从小的状态转移过来。
这个显然可以用单调队列维护。
具体的说，每次我们计算出来的 $ f[i] $，假设它可以用来更新 $ f[j] $ ，那么对于 $j$ 及其以后的状态，都不用考虑 $1 \cdots i-1$ 的状态来转移了。那么我们要做的就是每次我们计算出 $ f[i] $ ，我们找到一个 $f[j]$ ，满足由 $i$ 转移到 $j$ 比$1\cdots i-1$ 更优。由于决策的单调性，可以二分来查找 $j$。最后用单调队列来保存一下决策即可。
<h3>代码</h3>
输出真毒瘤
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define R register
#define LL long long
#define U unsigned
#define LD long double
#define FOR(i,a,b) for(R int i = a;i <= b;++i)
#define RFOR(i,a,b) for(R int i = a;i >= b;--i)
#define CLR(i,a) memset(i,a,sizeof(i))
#define BR printf("--------------------n")
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
// f[i] = std::min(f[j] + (sum[i]-sum[j]L-1)^P)
const int MAXN = 100000 + 5;
const int MAXL = 30 + 5;
int N,L,P;
char strMAXN;
int sum[MAXN],k[MAXN],pr[MAXN];
LD f[MAXN];
int q[MAXN],head,tail;
inline LD qpow(LD a,int n){
LD ret = 1;
while(n){
if(n & 1) ret = ret * a;
a = a * a;
n >>= 1;
}
return ret;
}
inline LD query(int i,int j){
return f[j] + qpow(std::abs(sum[i]-sum[j]-L),P);
}
inline int bound(int x,int y){
int l = x,r = N + 1;
while(l < r){
int mid = (l + r) >> 1;
if(query(mid,x) >= query(mid,y)) r = mid;
else l = mid + 1;
}
return l;
}
inline void Solve(){
scanf("%d%d%d",&N,&L,&P);L++;
FOR(i,1,N){
scanf("%s",str[i]);
sum[i] = sum[i-1] + strlen(str[i]) + 1;
}
head = tail = 1;
q[head] = 0;
FOR(i,1,N){
while(head < tail && k[head] <= i) head++;
f[i] = query(i,q[head]);
pr[i] = q[head];
while(head < tail && k[tail-1] >= bound(q[tail],i)) --tail;
k[tail] = bound(q[tail],i);q[++tail] = i;
}
if(f[N] > 1e18) puts("Too hard to arrange");
else{
printf("%.0Lfn",f[N]);
tail = 0;
q[tail] = N;
int i = N;
while(i){
q[++tail] = i = pr[i];
}
while(tail){
for(i=q[tail]+1;i < q[tail-1];i++)
printf("%s ",str[i]);
puts(str[i]);
tail--;
}
}
puts("--------------------");
}
int main(){
int T;
scanf("%d",&T);
while(T--){
Solve();
}
return 0;
}
