动态规划
Time Limit: 50 Sec Memory Limit: 128 MB
Description
一开始有n个数，一段区间的价值为这段区间相同的数的对数。
我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。
我们想让最终这n个数的价值和尽可能少。
例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。
我们想把这n个数切成恰好k段区间。之后这n个数的价值为这k段区间的价值和。
我们想让最终这n个数的价值和尽可能少。
例如6个数1,1,2,2,3,3要切成3段，一个好方法是切成[1],[1,2],[2,3,3]，这样只有第三个区间有1的价值。因此这6个数的价值为1。
Input
第一行两个数n,k。
接下来一行n个数ai表示这n个数。
接下来一行n个数ai表示这n个数。
Output
一个数表示答案。
Sample Input
10 2
1 2 1 2 1 2 1 2 1 2
1 2 1 2 1 2 1 2 1 2
Sample Output
8
HINT
对于100%的数据1<=n<=100000,1<=k<=min(n,20),1<=ai<=n。
Solution
首先，暴力DP非常显然，f[i][j] 表示分了 i 段，当前做到第 j 个元素的最小值。
那么 f[i][j] = f[i - 1][k] + sum(k + 1, i)。我们打一个表，发现决策具有单调性。
但是显然，对于这道题，我们不能直接二分转移来的位置，由于sum并不好求。
所以我们可以考虑运用分治。执行k次。Solve(l, r, L, R)表示 j∈[l, r]，from∈[L, R]。
那么我们对于[l, r]，考虑mid从[L, R]中的哪一个转移过来，假设是MidFrom。
那么由于决策单调性，所以[l, mid - 1]的决策点一定在[L, MidFrom]，[mid + 1, r]的决策点一定在[MidFrom, R]。
移动两个指针now_l, now_r，维护sum即可。（复杂度我也不会证明呀QWQ）
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long s64; const int ONE = ;
const int MOD = 1e9 + ;
const s64 INF = 1e18; int get()
{
int res = , Q = ; char c;
while( (c = getchar()) < || c > )
if(c == '-') Q = -;
if(Q) res = c - ;
while( (c = getchar()) >= && c <= )
res = res * + c - ;
return res * Q;
} int n, k;
int a[ONE], cnt[ONE]; s64 record[ONE], f[ONE], value;
int now_l, now_r; void Move(int l, int r)
{
while(now_r < r) cnt[a[++now_r]]++, value += cnt[a[now_r]];
while(l < now_l) cnt[a[--now_l]]++, value += cnt[a[now_l]];
while(now_r > r) value -= cnt[a[now_r]], cnt[a[now_r--]]--;
while(l > now_l) value -= cnt[a[now_l]], cnt[a[now_l++]]--;
} void Solve(int l, int r, int L, int R) //j=l~r, from = L~R
{
if(l > r) return;
int mid = l + r >> , MidFrom;
s64 Ans = INF;
for(int from = L; from <= R; from++)
{
if(from >= mid) break;
Move(from + , mid);
if(f[from] + value < Ans)
Ans = f[from] + value, MidFrom = from;
}
record[mid] = Ans;
Solve(l, mid - , L, MidFrom);
Solve(mid + , r, MidFrom, R);
} int main()
{
n = get(); k = get();
for(int i = ; i <= n; i++)
a[i] = get(); for(int i = ; i <= n; i++) f[i] = INF;
f[] = ;
for(int j = ; j <= k; j++)
{
for(int i = ; i <= n; i++) cnt[i] = -;
now_l = now_r = ; value = , cnt[a[]] = ;
Solve(, n, , n - );
for(int i = ; i <= n; i++)
f[i] = record[i], record[i] = ;
}
printf("%lld", f[n]);
}