CF868 F. Yet Another Minimization Problem 决策单调优化 分治

---

目录

• [TOC]

题目链接

CF868F. Yet Another Minimization Problem

题解

\(f_{i,j}=\min\limits_{k=1}^{i}\{f_{k,j-1}+w_{k,i}\}\)

\(w_{l,r}\)为区间\([l,r]\)的花费,1D1D的经典形式

发现这个这是个具有决策单调性的转移

单无法快速转移,我们考虑分治

对于当前分治区间\([l,r]\) ,它的最优决策区间在\([L,R]\)之间。

对于\([l,r]\)的中点\(mid\)，我们可以暴力扫\([L−mid]\)

找到mid的最优决策点p。因为决策单调，所以\([l,mid−1]\)最优决策区间为\([L,p]\)，而\([mid+1,r]\),的最优决策区间在\([p,R]\)上

分治下去

求解区间：\(|\gets预处理\to | l\frac{\qquad\qquad\qquad\downarrow^{mid}\qquad\qquad\qquad}{}r\)

决策区间：\(L\frac{\qquad\qquad\qquad\downarrow^{p}\qquad\qquad\qquad}{}R\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = gc;

	while(c < '0' || c > '9' )c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f ;

}

void print(LL x) {

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

	 pc(x % 10 + '0');

}

int n,K;

const int maxn = 200007;

int a[maxn],b[maxn],c[maxn];

LL f[maxn],dp[maxn];

void solve(int l,int r ,int L,int R,int w) {

	if(l > r) return ;

	int mid = l + r >> 1,k = 0,p = std::min(mid,R);

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

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

		w -= -- c[a[i]];

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

	}

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

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

	solve(l,mid - 1,L,k,w);

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

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

	solve(mid + 1,r,k,R,w);

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

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

}

int main() {

	n = read(),K = read();

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

		f[i] = f[i - 1] + c[a[i] = read()] ++;

	memset(c,0,sizeof c);

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

		memset(dp,0x3f,sizeof dp);

		solve(1,n,1,n,0);

		std::swap(f,dp);

	}

	print(dp[n]);

	return 0;

}