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

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

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

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

 

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

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

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

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

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline int read(){10     #define num ch-'0'11     char ch;bool flag=0;int res;12     while(!isdigit(ch=getc()))13     (ch=='-')&&(flag=true);14     for(res=num;isdigit(ch=getc());res=res*10+num);15     (flag)&&(res=-res);16     #undef num17     return res;18 }19 const int N=1e5+5;20 int a[N],c[N],n,k;21 ll ff[N],gg[N],*f=ff,*g=gg;22 void solve(int l,int r,int kl,int kr,ll w){23     if(l>r) return;24     int m=l+r>>1,k=0,p=m
        
         f[i]+w?g[m]=f[i]+w,k=i:0;27     for(int i=kl;i<=p;++i) w+=c[a[i]]++;28     for(int i=l;i<=m;++i) w-=--c[a[i]];29     solve(l,m-1,kl,k,w);30     for(int i=l;i<=m;++i) w+=c[a[i]]++;31     for(int i=kl;i