Yet Another Minimization Problem
神仙题。
第一眼看上去就是 DP。
定义 \(f_{i,j}\) 表示当前点 \(i\),分 \(j\) 段的最小费用。
\(f_{i,j}= \min(f_{i,j},f_{k,j-1}+val_{k+1,i})\)
然后发现复杂度 \(O(n^2k)\),直接 T 飞,需要优化。
我们发现 \(j\) 那一维可以滚掉,也就是只考虑第一维,然后做 \(j\) 次就行了,下面称 \(f_{i,j}\) 为 \(f_i\)。
对于 \(val_{i,j}\),我们发现当 \(j\) 固定时,\(i\) 越小,值越大 (废话。
接下来最关键的一步就是证明转移的最优决策点是单调不降的。
我们考虑反证法。
定义 \(u\) 为当前点 \(i\) 的最优决策点,\(v\) 为 \(i+1\) 的最优决策点。
那么 \(f_u+\operatorname{val}(u+1,i) \le f_v+\operatorname{val}(v+1,i)\)
若 \(v < u\),则对于 \(i+1\) 应当满足:\(f_v+\operatorname{val}(v+1,i+1) \le f_u+\operatorname{val}(u+1,i+1)\)
即:\(f_v+\operatorname{val}(v+1,i)+ \Delta v \le f_u+\operatorname{val}(u+1,i)+ \Delta u\)
根据之前发现的单调性,显然可以得出 \(\Delta v \ge \Delta u\),即 \(\Delta v-\Delta u \ge 0\)。
所以移项可得 \(f_u+\operatorname{val}(u+1,i) \ge f_v+\operatorname{val}(v+1,i)+(\Delta v-\Delta u)\),与前者矛盾,证毕。
接下来就可以用分治来优化了。
定义 \(\operatorname{cal}(l,r,L,R)\) 为当前处理的区间 \([l,r]\) 和可能的最优决策点所在区间 \([L,R]\)。
对于一个这样的函数,我们可以暴力找到 \(mid=\left\lfloor l+r \right\rfloor\) 的最优决策点 p, 然后递归下去。
那么问题来了,怎么快速求出 \(\operatorname{val}(l,r)\) 呢?直接莫队就行了!
复杂度 \(O(kn \log n+n \sqrt n)\) 。
code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 5, inf = LLONG_MAX >> 1;
ll n, k, a[N], cnt[N], lm = 1, rm = 0, ans = 0, f[N], g[N];
void add(ll w) {
ans += cnt[a[w]];
++cnt[a[w]];
}
void del(ll w) {
--cnt[a[w]];
ans -= cnt[a[w]];
}
ll val(ll l, ll r) {
while (lm > l) add(--lm);
while (lm < l) del(lm++);
while (rm > r) del(rm--);
while (rm < r) add(++rm);
return ans;
}
void dfs(ll l, ll r, ll L, ll R) {
if (l > r) return;
ll mid = (l + r) >> 1, mid2 = L, minn = inf;
for (ll i = L; i <= min(R, mid); ++i) {
if (f[i - 1] + val(i, mid) < minn) {
minn = f[i - 1] + val(i, mid);
mid2 = i;
}
}
g[mid] = minn;
dfs(l, mid - 1, L, mid2); dfs(mid + 1, r, mid2, R);
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> k;
for (ll i = 1; i <= n; ++i) cin >> a[i], f[i] = inf;
for (ll i = 1; i <= k; ++i) {
dfs(1, n, 1, n);
for (ll j = 1; j <= n; ++j) f[j] = g[j], g[j] = inf;
}
cout << f[n] << endl;
return 0;
}
- 题解 Minimization Another Problem Yet题解minimization another problem inversions another problem yet minimization another problem 1637d another problem 1073g yet 题解permutation another problem 题解another problem 1870e another monster fight yet 题解another maxflow problem 题解counting another problem 题解inversions another problem