决策单调性优化 DP

我们讨论形如

\[ f_i=\min_{j<i}\{w(j,i)\} \]

的转移式，\(w(j,i)\) 可以看成一个 \(n\times n\) 的矩阵。

决策单调性

若 \(w(j,i)\) 取到最小值的 \(j\) 随 \(i\) 单调不降，那么称 \(w\) 具有决策单调性。

对于任意 \(p\in [1,n]\)，若只考虑 \(j\le p\) 的部分，决策点仍然单调不降，那么称 \(w\) 具有完全决策单调性。

四边形不等式

若 \(w(j,i)\) 对任意的 \(a\le b\le c\le d\) 都满足

\[ w(a,c)+w(b,d)\le w(a,d)+w(b,c) \]

则称 \(w(j,i)\) 满足四边形不等式。

性质 1：\(w\) 满足四边形不等式的充要条件是，对任意的 \(a\le b\le c\)，满足 \(w(a,c+1)-w(a,c)\ge w(b,c+1)-w(b,c)\)。即，给长区间加一个元素，比给短区间加一个元素代价更大。 性质 2：若 \(w\) 满足四边形不等式，则 \(w\) 满足完全决策单调性。

二分队列

当 \(w\) 满足完全决策单调性的时候，可以使用二分队列。二分队列的转移是在线的。

依次加入每一个 \(j\)，注意到一个 \(j\) 只会影响到一个后缀 \(i\)，因此用单调队列维护决策点，找到分界点所在的段并在段内部进行二分即可。

P3195 [HNOI2008] 玩具装箱

模板

#include<iostream>
#include<deque>
#define int long long
using namespace std;
const int N = 5E4 + 10;

struct myPair {
    int l, r, p;
};

int n, c;
int s[N], f[N];

inline int w(int l, int r) {
    return (s[r] - s[l] + c) * (s[r] - s[l] + c);
}

myPair que[N];
int hd = 1, tl;

signed main() {

    cin >> n >> c;
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1] + 1;
    }

    c = -c - 1;

    que[++tl] = {1, n, 0};

    for(int i = 1; i <= n; i++) {
        if(que[hd].r < i) hd++;
        que[hd].l = i;
        f[i] = f[que[hd].p] + w(que[hd].p, i);
        while(hd <= tl && f[i] + w(i, que[tl].l) < f[que[tl].p] + w(que[tl].p, que[tl].l)) --tl;
        if(hd > tl) {
            que[++tl] = {i + 1, n, i};
            continue;
        }
        int l = que[tl].l, r = que[tl].r + 1, p = que[tl].p;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(f[i] + w(i, mid) < f[p] + w(p, mid)) {
                r = mid;
            } else l = mid + 1;
        }
        que[tl].r = l - 1;
        if(l <= n) que[++tl] = {l, n, i};
    }

    cout << f[n] << endl;

    return 0;
}

P3515 [POI 2011] Lightning Conductor

给定一个长为 \(n\) 的数列 \(a_i\)，你需要对每个 \(i\) 求出

\[ \max_{j=1}^{i-1}\{\Big\lceil a_j+\sqrt{i-j}\Big\rceil \} \]

注意

\(y=\sqrt{x}\) 是上凸函数，但 \(y=\Big\lceil\sqrt{x}\Big\rceil\) 不具有凸性。因此本题需要在浮点数类型下计算，将上取整提到 \(\max\) 外。

注意到 \(w(j,i)=-\sqrt{i-j}\) 具有凸性，满足四边形不等式。直接套用模板即可。

代码

#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
#define ld long double
using namespace std;
const int N = 5E5 + 10;
const ld eps = 1e-8;

struct Range {
    int l, r, p;
};

int n;
int a[N];
ld w[N], mx[N];

Range que[N];
int hd, tl;

signed main() {

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for(int i = 1; i <= n; i++) {
        w[i] = sqrt(i);
    }

    hd = 1, tl = 0;
    que[++tl] = {1, n, 1};
    for(int i = 2; i <= n; i++) {
        if(que[hd].r < i) hd++;
        que[hd].l = i;
        mx[i] = max(mx[i], a[que[hd].p] + w[i - que[hd].p]);
        while(hd < tl && a[i] + w[que[tl].l - i] >= a[que[tl].p] + w[que[tl].l - que[tl].p]) --tl;
        int l = que[tl].l, r = que[tl].r + 1, p = que[tl].p;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(a[i] + w[mid - i] >= a[p] + w[mid - p]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        que[tl].r = l - 1;
        if(l <= n) que[++tl] = {l, n, i};
    }

    // 因为原题没有限制 j<i，因此需要反着跑一边 DP
    reverse(a + 1, a + 1 + n);

    hd = 1, tl = 0;
    que[++tl] = {1, n, 1};
    for(int i = 2; i <= n; i++) {
        if(que[hd].r < i) hd++;
        que[hd].l = i;
        mx[n - i + 1] = max(mx[n - i + 1], a[que[hd].p] + w[i - que[hd].p]);
        while(hd <= tl && a[i] + w[que[tl].l - i] >= a[que[tl].p] + w[que[tl].l - que[tl].p]) --tl;
        if(hd > tl) {
            que[++tl] = {i + 1, n, i};
            continue;
        }
        int l = que[tl].l, r = que[tl].r + 1, p = que[tl].p;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(a[i] + w[mid - i] >= a[p] + w[mid - p]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        que[tl].r = l - 1;
        if(l <= n) que[++tl] = {l, n, i};
    }

    for(int i = 1; i <= n; i++) {
        // 向上取整
        cout << max((int)(mx[i] + 1 - eps) - a[n - i + 1], 0ll) << '\n';
    }

    return 0;
}

P1912 [NOI2009] 诗人小G

代码

#include<iostream>
#include<cstring>
#define int long long
#define ld long double
using namespace std;
const int N = 1E5 + 10;
const ld V = 1E18;
const ld INF = 1E20;

struct myPair {
    int l, r, p;
};

int T;
int n, L, P;

int s[N], p[N];
ld f[N];
char str[N][40];

myPair que[N];
int hd, tl;

inline ld qpow(ld a, int b) {
    ld res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

inline ld w(int i, int j) {
    return qpow(abs(s[j] - s[i] - L - 1), P);
}

void solve() {
    hd = 1, tl = 0;
    que[++tl] = {1, n, 0};
    for(int i = 1; i <= n; i++) {
        if(que[hd].r < i) hd++;
        que[hd].l = i;
        f[i] = f[que[hd].p] + w(que[hd].p, i);
        p[i] = que[hd].p;
        while(hd <= tl && f[i] + w(i, que[tl].l) < f[que[tl].p] + w(que[tl].p, que[tl].l)) --tl;
        if(hd > tl) {
            que[++tl] = {i + 1, n, i};
            continue;
        }
        int l = que[tl].l, r = que[tl].r + 1, p = que[tl].p;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(f[i] + w(i, mid) < f[p] + w(p, mid)) {
                r = mid;
            } else l = mid + 1;
        }
        que[tl].r = l - 1;
        if(l <= n) que[++tl] = {l, n, i};
    }
}

void outPut(int x) {
    if(x == 0) return;
    outPut(p[x]);
    for(int i = p[x] + 1; i <= x; i++) {
        for(int j = 0; j < s[i] - s[i - 1] - 1; j++) {
            cout << str[i][j];
        }
        if(i < x) cout << ' ';
    }
    cout << '\n';
}

signed main() {

    cin >> T;
    while(T--) {
        cin >> n >> L >> P;
        getchar();
        for(int i = 1; i <= n; i++) {
            cin.getline(str[i], 40, '\n');
            s[i] = strlen(str[i]);
            s[i] += s[i - 1] + 1;
        }
        for(int i = 1; i <= n; i++) f[i] = 0;
        for(int i = 1; i <= n; i++) que[i] = {0, 0, 0};
        solve();
        if(f[n] > V) {
            cout << "Too hard to arrange\n";
            cout << "--------------------\n";
            continue;
        }
        cout << (int)f[n] << '\n';
        outPut(n);
        cout << "--------------------\n";
    }

    return 0;
}

分治

分治法与二分队列不同，它只要求 \(w\) 满足决策单调性。并且，分治法一次只需要 \(w(j,i)\) 一列的一段区间。这在单个 \(w(j,i)\) 难以 \(O(1)\) 计算时非常管用。然而分治法只能处理离线的问题（好像有在线单 \(\log\) 分治做法，据说还挺简单的）。

CF1603D Artistic Partition

对于两个正整数 \(l,r\)（\(l\le r\)），定义 \(c(l,r)\) 表示满足 \(l\le x\le y\le r\) 且 \(\gcd(x,y)\ge l\) 的数对 \((x,y)\) 的数量。

对于两个正整数 \(n,k\)（\(k\le n\)），定义 \(f(n,k)\) 表示将 \([1,n]\) 区间划分为 \(k\) 段连续区间 \([l_1,r_1],[l_2,r_2],\cdots,[l_k,r_k]\)（\(l_1=1,\ r_k=n,\ l_i=r_{i-1}+1\)），\(\sum_{i=1}^k{c(l_i,r_i)}\) 的最小值。

多组询问，每次给定两个数 \(n,k\)，输出 \(f(n,k)\)。

\(T\le 3\times 10^5,\ 1\le k\le n\le 10^5\)

首先有一些显然的观察：若 \(r<2l\)，那么 \(c(l,r)=r-l+1\)。这样，当 \(n<2^k\) 时，答案可以取到最小值 \(n\)。其余情况 \(k\) 是 \(\log n\) 级别的。

考虑转移：

\[ f(n,k)=\min_{1\le i<n}\bigl\{f(i,k-1)+c(i+1,n)\big\} \]

\(c(l,r)\) 枚举数对 \((x,y)\) 似乎没什么前途，改为枚举 \(\gcd\)：

\[ \begin{align*} c(l,r)&=\sum_{d=l}^{r}\sum_{x=l}^{r}\sum_{y=x}^{r}[\gcd(x,y)=d]\\ &=\sum_{d=l}^{r}\sum_{y=1}^{\lfloor\frac rd\rfloor}\sum_{x=1}^{y}[\gcd(x,y)=1]\\ &=\sum_{d=l}^{r}\sum_{y=1}^{\lfloor\frac rd\rfloor}\varphi(y)\\ &=\sum_{d=l}^{r}s\bigl(\lfloor\frac rd\rfloor\bigr) \end{align*} \]

其中 \(s(x)\) 表示欧拉函数前缀和。这个式子可以用数论分块做到单次 \(O(\sqrt n)\)。

考察 \(c(a,d)+c(b,c)-c(a,c)-c(b,d)\)：

\[ \begin{align*} c(a,d)+c(b,c)-c(a,c)-c(b,d)&=\bigl(c(a,d)-c(b,d)\big)-\bigl(c(a,c)-c(b,c)\big)\\ &=\sum_{i=a}^{b-1}s(\lfloor\frac di\rfloor)-s(\lfloor\frac ci\rfloor) \end{align*} \]

由于 \(s(x)\) 单调递增，因此上式显然非负，因此 \(c(l,r)\) 满足四边形不等式，相应可以进行决策单调性优化。时间复杂度来到 \(O(n\sqrt n\log^2 n)\)。

实际上，我们无需推式子就可以判断出四边形不等式。考虑性质 1，显然长区间加一个东西的代价比短区间加一个东西的代价大。证毕。

注意到 \(c(l,r)\) 和 \(r\) 强相关，容易得出递推式 \(c(l,r)=c(l+1,r)+s(\lfloor\frac rl\rfloor)\)。因此考虑分治法。分治法一次需要 \(r\) 相等时 \(l\) 的一段区间。这样做似乎是对的，我不太会分析。

实际上我们可以 \(O(n\sqrt n)\) 预处理，\(O(1)\) 查询 \(c(l,r)\)。注意到数论分块的第一次迭代后，\(p\gets \left\lfloor\frac r{\lfloor\frac rp\rfloor}\right\rfloor\) 只有 \(O(\sqrt r)\) 种取值。因此预处理出第一次迭代后，\((r,p)\) 的所有答案即可。

代码

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;

int T;
int n, m;

int npri[N], pri[N], pcnt;
int phi[N], s[N];

int f[25][N];

int calc(int l, int r) {
    int res = 0;
    for(int i = l, j; i <= r; i = j + 1) {
        j = min(r, r / (r / i));
        res += (j - i + 1) * s[r / i];
    }
    return res;
}

void solve(int i, int l, int r, int tl, int tr) {
    if(l > r) return;
    int mid = (l + r) >> 1;
    int w = calc(tr + 1, mid);
    int mp = tl;
    f[i][mid] = INF;
    for(int j = min(tr, mid); j >= tl; j--) {
        w += s[mid / j];
        if(f[i - 1][j - 1] + w < f[i][mid]) {
            f[i][mid] = f[i - 1][j - 1] + w;
            mp = j;
        }
    }
    solve(i, l, mid - 1, tl, mp);
    solve(i, mid + 1, r, mp, tr);
}

signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    phi[1] = 1;
    for(int i = 2; i < N; i++) {
        if(!npri[i]) {
            pri[++pcnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] >= N) break;
            npri[i * pri[j]] = 1;
            if(i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            } else phi[i * pri[j]] = phi[i] * (pri[j] - 1);
        }
    }

    for(int i = 1; i < N; i++) s[i] = s[i - 1] + phi[i];

    m = 18;
    n = 100000;

    for(int i = 1; i <= n; i++) f[0][i] = INF;
    for(int i = 1; i <= n; i++) f[1][i] = i * (i + 1) / 2;

    for(int i = 2; i <= m; i++) {
        solve(i, 1, n, 1, n);
    }

    cin >> T;
    while(T--) {
        cin >> n >> m;
        if(m > 18 || n < (1 << m)) {
            cout << n << '\n';
        } else cout << f[m][n] << '\n';
    }

    return 0;
}