CF868F Yet Another Minimization Problem（决策单调性）

题目描述：给定一个序列，要把它分成k个子序列。每个子序列的费用是其中相同元素的对数。求所有子序列的费用之和的最小值。

输入格式：第一行输入n（序列长度）和k（需分子序列段数）。下一行有n个数，序列的每一个元素。

输出格式：输出一个数，费用和的最小值。

2<=n<=10^5,2<=k<=min(n,20),序列的每一个元素值大于等于1，小于等于n。

决策单调性到底是个什么神仙……

这题用分治做决策单调性……

问题是我连题解都看不懂……

米娜桑自己看题解吧，如果有会了的麻烦教我一下……->这里

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #define ll long long

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=1e5+;

 int a[N],c[N],n,k;

 ll ff[N],gg[N],*f=ff,*g=gg;

 void solve(int l,int r,int kl,int kr,ll w){

     if(l>r) return;

     int m=l+r>>,k=,p=m<kr?m:kr;

     for(int i=l;i<=m;++i) w+=c[a[i]]++;

     for(int i=kl;i<=p;++i) w-=--c[a[i]],g[m]>f[i]+w?g[m]=f[i]+w,k=i:;

     for(int i=kl;i<=p;++i) w+=c[a[i]]++;

     for(int i=l;i<=m;++i) w-=--c[a[i]];

     solve(l,m-,kl,k,w);

     for(int i=l;i<=m;++i) w+=c[a[i]]++;

     for(int i=kl;i<k;++i) w-=--c[a[i]];

     solve(m+,r,k,kr,w);

     for(int i=kl;i<k;++i) ++c[a[i]];

     for(int i=l;i<=m;++i) --c[a[i]];

 }

 int main(){

     //freopen("testdata.in","r",stdin);

     n=read(),k=read();

     ll *tmp;

     for(int i=;i<=n;++i) f[i]=f[i-]+c[a[i]=read()]++;

     memset(c,,sizeof(c));

     while(--k){

         memset(g,,(n+)<<);

         solve(,n,,n,);

         tmp=f,f=g,g=tmp;

     }

     printf("%lld\n",f[n]);

     return ;

 }