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;
}
标签:cnt,Minimization,val,题解,ll,Delta,rm,Problem,operatorname
From: https://www.cnblogs.com/HQJ2007/p/17561298.html