【CodeForces】868F. Yet Another Minimization Problem

原题链接

题目大意是有N个数，分成K段，每一段的花费是这个数里相同的数的数对个数，要求花费最小

如果只是区间里相同数对个数的话，莫队就够了

而这里是！边单调性优化边莫队（只是类似莫队）！而移动的次数和分治的复杂度是一样的！

这个时候就不能用单调栈+二分了，得用分治

分治的方法就是\(Solve(l,r,ql,qr)\)表示我想计算区间\([l,r]\)的答案，然后转移过来的区间在\([ql,qr]\)

暴力计算出\(f[mid]\)的值，找到最优转移点是\(k\)，然后分成\(Solve(l,mid,ql,k)\)和\(Solve(mid +1,r,k,qr)\)做下去

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <bitset>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

template<class T>

void read(T &res) {

	res = 0;T f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {x = -x;putchar('-');}

	if(x >= 10) out(x / 10);

	putchar('0' + x % 10);

}

int N,K,a[MAXN],cnt[MAXN];

int64 f[22][MAXN],w = 0;

int nw,p,q;

int64 work(int l,int r) {

	while(q < r) w += cnt[a[++q]]++;

	while(p > l) w += cnt[a[--p]]++;

	while(p < l) w -= --cnt[a[p++]];

	while(q > r) w -= --cnt[a[q--]];

	return w;

}

int64 Calc(int a,int b) {

	return f[nw - 1][a] + work(a + 1,b);

}

void Solve(int l,int r,int ql,int qr) {

	if(l > r) return;

	int mid = (l + r) >> 1,p = min(qr,mid - 1);

	int k;

	f[nw][mid] = Calc(ql,mid);k = ql;

	for(int i = ql + 1 ; i <= p ; ++i) {

		int64 x = Calc(i,mid);

		if(x <= f[nw][mid]) {

			f[nw][mid] = x;k = i;

		}

	}

	Solve(l,mid - 1,ql,k);

	Solve(mid + 1,r,k,qr);

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	read(N);read(K);

	for(int i = 1 ; i <= N ; ++i) {read(a[i]);f[1][i] = f[1][i - 1] + cnt[a[i]]++;}

	for(int i = 2 ; i <= K ; ++i) {

		memset(cnt,0,sizeof(cnt));

		p = 1;q = 0;w = 0;

		nw = i;

		Solve(0,N,0,N);

	}

	out(f[K][N]);enter;

}