F. Yet Another Minimization Problem

http://codeforces.com/contest/868/problem/F

题意：

　　给定一个长度为n的序列。你需要将它分为m段，每一段的代价为这一段内相同的数的对数，最小化代价总和。 n<=100000，m<=20。

分析：

　　f[k][j]=min{f[k-1][j]+cost(k,j,i)};

　　cost发现不能快速的算出。于是不能用类似单调队列+二分的方法来做了。

　　考虑分治，solve(Head,Tail,L,R,w)当分治区间为Head,Tail，L,R为转移的区间，那么可以直接扫一遍找到转移的最优位置k，然后分治下去。分治的过程中，维护每个数出现了几次（cnt数组），在进入下一层的时候，更新了下层用到的区间的cnt。

代码：

 /*

 * @Author: mjt

 * @Date:   2018-10-15 11:28:17

 * @Last Modified by:   mjt

 * @Last Modified time: 2018-10-15 14:40:30

 */

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 int a[N], cnt[N];

 LL f[N], g[N];

 #define add(x) w += cnt[x], cnt[x] ++

 #define del(x) cnt[x] --, w-= cnt[x]

 void solve(int Head,int Tail,int L,int R,LL w) { // w保存(L~R)中，非(Head~Tail)，区间的值，即L~min(R,Head)。

     if (Head > Tail) return ;

     int mid  = (Head + Tail) >> , p = min(R, mid), k = ;

     for (int i=Head; i<=mid; ++i) add(a[i]);

     for (int i=L; i<=p; ++i) {

         del(a[i]); // 从i转移，所以i左边的数，不应该被算入贡献，所以要减去。

         if (f[mid] > g[i] + w) f[mid] = g[i] + w, k = i;

     }

     for (int i=Head; i<=mid; ++i) del(a[i]);

     for (int i=L; i<=p; ++i) add(a[i]);

     solve(Head, mid - , L, k, w); 

     for (int i=L; i<k; ++i) del(a[i]);

     for (int i=Head; i<=mid; ++i) add(a[i]);

     solve(mid + , Tail, k, R, w);

     for (int i=Head; i<=mid; ++i) del(a[i]); // 初始为递归进来时候的cnt数组。

     for (int i=L; i<k; ++i) add(a[i]);

 }

 int main() {

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

     for (int i=; i<=n; ++i) {

         a[i] = read();

         f[i] = f[i - ] + cnt[a[i]];

         cnt[a[i]] ++;

     }

     memset(cnt, , sizeof(cnt));

     while (-- k) {

         swap(f, g);

         memset(f, 0x3f, sizeof(f));

         solve(, n, , n, );

     }

     cout << f[n];

     return ;

 }

巴特西

CF 868 F. Yet Another Minimization Problem

F. Yet Another Minimization Problem

最新文章

热门文章