c/c++语言开发共享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 |) (lfrac{qquadqquadqquaddownarrow^{mid}qquadqquadqquad}{}r)

决策区间：(lfrac{qquadqquadqquaddownarrow^{p}qquadqquadqquad}{}r)

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

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

#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]; }