cf868F. Yet Another Minimization Problem(决策单调性 分治dp)

题意

题目链接

给定一个长度为\(n\)的序列。你需要将它分为\(m\)段，每一段的代价为这一段内相同的数的对数，最小化代价总和。

\(n<=10^5，m<=20\)

Sol

看完题解之后的感受：

首先列出裸的dp方程，\(f[i][j]\)表示前\(i\)个位置，切了\(j\)次，转移的时候枚举上一次且在了哪儿

\(f[i][j] = max(f[k][j - 1] + w(k, i))\)

\(w(k, i)\)表示\([k, i]\)内相同的数的对数。。

然后sb的我以为拿个单调队列维护一下就完了结果发现转移是\(O(n)\)的？？

标算真神仙Orz

因为转移不是\(O(n)\)的，所以我们可以分治的去做

假设当前要求的区间为\([l, r]\)，可以从\([L, R]\)转移而来，\(mid = (l + r)/ 2\)的决策点为\(p\)

那么\([l, mid - 1]\)的转移区间一定在\([L, p]\)，\([mid+1, r]\)的转移区间一定是\([p, R]\)，递归的做即可

画出图来应该是这样的

求解区间：\(|\gets\)预处理\(\to |\) \(l\frac{\qquad\qquad\qquad\downarrow^{mid}\qquad\qquad\qquad}{}r\)

决策区间：\(L\frac{\qquad\qquad\qquad\downarrow^{p}\qquad\qquad\qquad}{}R\)

转移的时候需要记录每个数的出现次数，每次转移时\(O(1)\)的

总的时间复杂度为：\(O(nlognk)\)

推荐一篇写的不错的blog

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int MAXN = 1e5 + 10;

inline int read() {

    int x = 0, f = 1; char c = getchar();

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, K, a[MAXN], b[MAXN];

LL f[MAXN], g[MAXN];

void solve(int l, int r, int L, int R, LL w) {

    if(l > r) return ;

    int mid = l + r >> 1, p = min(mid, R), k = 0;

    for(int i = l; i <= mid; i++) w += b[a[i]]++;

    for(int i = L; i <= p; i++)   w -= --b[a[i]], f[mid] > g[i] + w ? f[mid] = g[i] + w, k = i : 0;

    for(int i = l; i <= mid; i++) w -= --b[a[i]];

    for(int i = L; i <= p; i++)   w += b[a[i]]++;

    solve(l, mid - 1, L, k, w);

    for(int i = L; i < k; i++)    w -= --b[a[i]];

    for(int i = l; i <= mid; i++) w += b[a[i]]++;

    solve(mid + 1, r, k, R, w);

    for(int i = l; i <= mid; i++) --b[a[i]];

    for(int i = L; i < k; i++)    ++b[a[i]];

}

main() {

    N = read(); K = read();

    for(int i = 1; i <= N; i++) a[i] = read(), g[i] = g[i - 1] + b[a[i]]++; memset(b, 0, sizeof(b));

    while(K--) {memset(f, 0x7f, sizeof(f)); solve(1, N, 1, N, 0); swap(f, g);}

    cout << f[N];

}