决策单调性优化

发布于 2018-09-01  287 次阅读


写一些简单的 1D/1D 的决策单调性优化...

这种决策单调性优化的过程:列出方程 $\to$ 打表发现决策单调性 $\to$ 套单调队列/二分

我们以一些例题为例:

[ZROI普转提]Bead

题目链接

注:该题有权限,看不到的就看下一题。

这一题我们推出朴素的状态转移方程:

设 $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 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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 f[MAXN][MAXK],cnt[MAXN],t[MAXN];
int L,R,ans;
// f[i][k] = std::min(f[i][k],f[j-1][k-1] + w[j][i]);

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) f[l][k] = std::min(f[l][k],f[i-1][k-1] + query(i,l));
        return;
    }
    int mid = (l + r) >> 1;
    FOR(i,pl,pr)
        t[i] = f[i-1][k-1] + query(i,mid);
    int next = 0;
    FOR(i,pl,pr)
        if(!next || t[i] < t[next])
            next = i;
    f[mid][k] = 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));
    f[0][0] = 0;
    FOR(i,1,K) work(i,1,N,1,N);
    printf("%d\n",f[N][K]);
    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$。最后用单调队列来保存一下决策即可。

代码

~~输出真毒瘤~~

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#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 str[MAXN][MAXL];
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("%.0Lf\n",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;
}

一个OIer。