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)\)
#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]; }
上一篇: 小程序开发流程
下一篇: 云计算融入数据中心 资源调配无阻隔