[基本操作]决策单调性优化dp

一般的式子都是 $f_i = max\{g_j + w_{(i,j)}\}$

然后这个 $w$ 满足决策单调性，也就是对于任意 $i < j$ ，$best_i \leq best_j$

这样就会有两种优化方式

1.$w_{(i,j)}$ 可以快速求

例如：NOI 2009 诗人小 G

题里给了你 $L,P$ 和单调递增的 $s$ 数组，然后 $f_i = min \{ f_j + |s_i-s_j-L-1|^P \} \space (j < i)$

可以发现以一个点为最优决策的点是一段区间

我们可以用单调栈维护这个区间，具体地，在栈里存一个三元组 $(l,r,x)$ 表示 $[l,r]$ 的最优决策都在 $x$

一开始栈里只有一个区间 $(1,n,0)$，考虑对每次加入的 $i$，更新这个栈

1) 如果 $i$ 可以转移到当前的区间 $[l,r]$，且 $i$ 比 $x$ 优，我们发现 $i$ 完爆 $x$ ，没理由留着 $x$

2) 不管 $i$ 有没有完爆 $x$，因为决策单调性，$i$ 可以影响后面一段区间（$i$ 从左到右，所以当前的 $i$ 显然在 $x$ 右边，有可能成为后面某段区间的最优决策），我们在 $[min(L,i+1),R]$ 这段区间上二分找出一个位置 $p$ 满足 $p$ 以前 $x$ 最优，$p$ 及以后 $i$ 最优，把 $(p,n,i)$ 加入队列，并把 $(l,r,x)$ 改成 $(l,p-1,x)$（如果不存在 $p$ 就不加）

所以从左到右每次加入一个 $i$ ，更新它的 $f$ 数组，然后把它的贡献加入栈里就可以了

复杂度 $O(nlogn)$

#include<bits/stdc++.h>

#define LL long long

#define DB long double

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-') f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = ,maxw = ;

int n,l,p;

char s[maxn][maxw];

DB f[maxn];

int sum[maxn],top;

struct Deci

{

    int l,r,x;

    Deci(){}

    Deci(int _l,int _r,int _x){l = _l,r = _r,x = _x;}

}st[maxn];

inline DB calc(int j,int i)

{

    DB res = 1.0,cur = 1.0 * abs((sum[i] + i - sum[j] - j - ) - l);

    for(int i=;i<=p;i++)res *= cur;

    return res;

}

int main()

{

    int T = read();

    while(T--)

    {

        n = read(),l = read(),p = read();

        int cur = ;

        for(int i=;i<=n;i++)

        {

            scanf("%s",s[i] + );

            sum[i] = sum[i - ] + strlen(s[i] + );

        }

        st[top = ] = Deci(,n,);

        for(int i=;i<=n;i++)

        {

            f[i] = f[st[cur].x] + calc(st[cur].x,i);

            while(st[top].l > i && f[i] + calc(i,st[top].l) < f[st[top].x] + calc(st[top].x,st[top].l))top--;

            int L = max(i + ,st[top].l),R = st[top].r,ans;

            while(L <= R)

            {

                int mid = (L + R) >> ;

                if(f[i] + calc(i,mid) < f[st[top].x] + calc(st[top].x,mid))R = mid - ;

                else L = mid + ;

            }

            st[top].r = L - ;

            if(L <= n)st[++top] = Deci(L,n,i);

            if(st[cur].r == i)cur++;

        }

        if(f[n] > 1e18)puts("Too hard to arrange");

        else printf("%lld\n",(LL)f[n]);

        puts("--------------------");

    }

}

2.$w_{(i,j)}$ 不能快速求

例如：Lydsy1712 月赛 Problem D. 小 Q 的书架

把一个数列分成 $k$ 段，最小化 $\sum$ 每一段内的逆序对

$n \leq 40000,k \leq 10$

先吐槽，这个数据范围给我，我绝对不去莫队

区间逆序对好像不是很可算，只能莫队，但这个莫队还是动态查询，所以复杂度非常没有保障

然后 $w_{(i,j)}$ 虽然满足四边形不等式，但复杂度不是很对

可以分治，每次对于一个区间 $[l,r]$ 假设它的最优决策在 $[ql,qr]$ 上

令 mid=(l+r)>>1 ，我们可以暴力扫 $[l,mid]$ 找出它的最优决策点 $x$，然后递归解决 $[l,mid-1],[ql,x]$ 和 $[mid+1,r],[x,qr]$ 这两个子问题

这样做是 $O(nlogn)$ 的，复杂度证明同归并排序

#include<bits/stdc++.h>

#define LL long long

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-') f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = ;

int n,k;

int c[maxn],a[maxn],f[maxn],g[maxn];

inline int lowbit(int x){return x & (-x);}

inline void add(int x,int v){for(;x <= n;x += lowbit(x))c[x] += v;}

inline int cal(int x){int res = ;for(;x;x -= lowbit(x))res += c[x];return res;}

int nl,nr,ans;

inline void Get(int l,int r)

{

    while(nl > l)nl--,ans += cal(a[nl] - ),add(a[nl],);

    while(nr < r)nr++,ans += cal(n) - cal(a[nr]),add(a[nr],);

    while(nl < l)add(a[nl],-),ans -= cal(a[nl] - ),nl++;

    while(nr > r)add(a[nr],-),ans -= cal(n) - cal(a[nr]),nr--;

}

void solve(int l,int r,int L,int R)

{

    if(l > r)return;

    int mid = (l + r) >> ,x;

    for(int i=min(mid,R+);i>L;i--)

    {

        Get(i,mid);

        if(g[i - ] + ans < f[mid])f[mid] = g[i - ] + ans,x = i - ;

    }

    solve(l,mid - ,L,x);solve(mid + ,r,x,R);

}

int main()

{

    n = nr = read();nl = ;

    k = read();

    for(int i=;i<=n;i++)

    {

        a[i] = read();

        f[i] = f[i - ] + cal(n) - cal(a[i]);

        add(a[i],);

    }ans = f[n];

    for(int i=;i<=k;i++)

    {

        for(int i=;i<=n;i++)g[i] = f[i],f[i] = 1e9;

        solve(,n,,n - );

    }

    cout<<f[n]<<endl;

}

巴特西

[基本操作]决策单调性优化dp

最新文章

热门文章