题目描述
LYK在学习dp，有一天它看到了一道关于dp的题目。
这个题目是这个样子的：一开始有n个数，一段区间的价值为这段区间相同的数的对数。我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。我们想让最终这n个数的价值和尽可能少。
例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。
LYK并不会做，丢给了你。
输入格式(dp.in)
第一行两个数n,k。
接下来一行n个数ai表示这n个数。
输出格式(dp.out)
一个数表示答案。
输入样例
10 2
1 2 1 2 1 2 1 2 1 2
输出样例
8
数据范围
对于30%的数据n<=10。
对于60%的数据n<=1000。
对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。
其中有30%的数据满足ai完全相同均匀分布在所有数据中。
分析：很容易想到dp的做法，设f[i][j]表示前i个数中分成了k个区间的最小价值和.
f[i][j] = min{f[k][j-1] + sum[k+1][i]}.这样dp只有60分，需要优化.注意到当j不变时，i增长，k是一定不减的.因为如果f[i+1][j]能从k前面转移过来，那么f[i][j]一定也能从k前面转移过来，这与f[i][j]从k转移过来是自相矛盾的，所以k一定不减.那么可以用1D1D优化.
类似分治，如果f[mid][j]从f[pos][j-1]转移而来，那么f[l~mid-1][j]一定从f[l'~pos][j-1]转移而来，f[mid + 1~r][j]一定从f[pos~r'][j-1]转移而来，递归下去，就能更新完所有答案.因为涉及到多次的区间求相同数对的个数，可以像莫队一样用两个指针来维护.
复杂度一般就是把朴素dp的一个n变成log,这道题的复杂度就是O(n*logn*k).
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const ll inf = 1LL << 60; ll f[100010], n, k, a[100010], c[100010], g[100010], L = 1, R = 0, tot, pos, mx; void move(int l, int r) { while (L < l) { c[a[L]]--; tot -= c[a[L]]; L++; } while (L > l) { L--; tot += c[a[L]]; c[a[L]]++; } while (R < r) { R++; tot += c[a[R]]; c[a[R]]++; } while (R > r) { c[a[R]]--; tot -= c[a[R]]; R--; } } void solve(ll l, ll r, ll x, ll y) { if (x > y) return; ll mid = (x + y) >> 1; mx = inf; for (ll i = l; i <= r; i++) if (i < mid) //mid只能从比mid小的地方转移过来 { move(i + 1, mid); if (f[i] + tot < mx) { mx = f[i] + tot; pos = i; } } g[mid] = mx; solve(l, pos, x, mid - 1); solve(pos, r, mid + 1, y); } int main() { scanf("%lld%lld", &n, &k); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); for (int i = 1; i <= n; i++) f[i] = inf; while (k--) { memset(c, 0, sizeof(c)); L = 1; R = 0; tot = 0; solve(0, n - 1, 1, n); memcpy(f, g, sizeof(g)); memset(g, 0, sizeof(g)); } printf("%lld ", f[n]); return 0; }