标签：二分，DP
You are given an array ofn integersa1... an. The cost of a subsegment is thenumber of unordered pairs of distinct indices within the subsegment thatcontain equal elements. Split the given array intok non-intersectingnon-empty subsegments so that the sum of their costs is minimum possible. Eachelement should be present in exactly one subsegment.
Input
The first line contains two integersnand k (2 ≤ n ≤ 105, 2 ≤ k ≤ min (n, 20)) — the length of the array and the number of segments youneed to split the array into.
The next line containsn integers a1, a2, ..., an (1 ≤ ai ≤ n) — the elements of the array.
Output
Print single integer: the minimum possibletotal cost of resulting subsegments.
Examples
Input
7 3
1 1 3 3 3 2 1
Output
1
Input
10 2
1 2 1 2 1 2 1 2 1 2
Output
8
Input
13 3
1 2 2 2 1 2 1 1 1 2 2 1 1
Output
9
Note
In the first example it's optimal to splitthe sequence into the following three subsegments: [1], [1, 3], [3, 3, 2, 1]. The costs are 0, 0 and 1, thus the answer is 1.
In the second example it's optimal to splitthe sequence in two equal halves. The cost for each half is 4.
In the third example it's optimal to splitthe sequence in the following way: [1, 2, 2, 2, 1], [2, 1, 1, 1, 2], [2, 1, 1]. The costs are 4,4, 1.
题意：给定：长度为N的序列a[1..N]，使其分成k个连续子序列
求：分割的最小代价，代价的定义为sum{每个连续子序列中出现的重复数对个数}
二分+动态规划
F数组记录答案，g数组记录二分时的状态
Code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL unsigned long long
using namespace std;
const int maxn=100006,inf=0x3f3f3f;
int n,k,a[maxn],t[maxn],p,q;
LL f[maxn],g[maxn],now;//防止答案过大，用long long存储
void solve(int l1,int r1,int l2,int r2){
//以l1,r1为标准范围进行二分
if(l1>r1)return;
int mid=(l1+r1)/2,temp=min(r2,mid);
LL mv=1e19;
while(q<mid)now+=t[a[++q]]++;
while(p>temp+1)now+=t[a[--p]]++;
while(q>mid)now-=--t[a[q--]];
while(p<temp+1)now-=--t[a[p++]];//使p,q不断接近now和temp+1
dep(i,temp,l2){
int x=a[i];
now+=t[a[--p]]++;
if(now+f[i-1]<mv)mv=now+f[i-1],temp=i;//选取最小的now+f[i-1]替换mv
}
g[mid]=mv;
solve(l1,mid-1,l2,temp);
solve(mid+1,r1,temp,r2);
}
int main()
{
scanf("%d%d",&n,&k);
rep(i,1,n)scanf("%d",&a[i]);
mem(f,inf);
f[0]=0;
rep(i,1,k){
p=1,q=now=0;
mem(t,0);
solve(i,n,i,n);
memcpy(f,g,sizeof f);
}
printf("%I64d\n",f[n]);
return 0;
}
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr
