CF868F Yet Another Minimization Problem 题解

CF868F Yet Another Minimization Problem

前言：

但是题解区没有 bfs 做得的，而且 bfs 复杂度极易证明，所以来交一篇题解。

类似整体二分的分治方法优化决策单调性 dp。

当然你可以打表输出决策点。

证明就看这道题的题解吧，我也是看的题解。

这里说一下我的实现方式：

外层遍历

k

。

对于每一层：我们还是设一个

\{l,r,ql,qr\}

表示 dp 数组下标

\in [ql,qr]

，决策点一定

\in [l,r]

。

设

mid=\frac{ql+qr}{2}

。

然后我们暴力遍历决策点区间尝试转移

dp_{mid}

，记录一个

p

表示决策点

p

可以使

dp_{mid}

最小。

由于决策单调性，dp 下标

\in [ql,mid)

的决策点一定

\in [l,p]

，dp 下标

\in (mid,qr]

的决策点一定

\in [p,r]

。继续分治求解即可。

边界是下标集合为空或决策点集合为空。

对于快速算一个区间的费用，可以用一个类似莫队的方法（可看成双指针）维护。

为了使复杂度正确，并且易于分析复杂度，可以使用 bfs 分治树的方法进行求解。

具体的，维护一个元素为

\{l,r,ql,qr\}

的队列，每次取出队首，还是按照上面说的方法做，但是将最后分治求解改为队列中依次加入元素

\{l,p,ql,mid-1\}

和

\{p,r,mid+1,qr\}

。

发现分治树深度为

\log n

，对于每一层，对答案造成贡献的区间指针一定是向右移动，所以每一层复杂度为线性。

总时间复杂度

O(kn \log n)

，常数可能较大。

Code

CPP

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int Size=(1<<20)+1;
char buf[Size],*p1=buf,*p2=buf;
char buffer[Size];
int op1=-1;
const int op2=Size-1;
#define getchar()                                                              \
(tt == ss && (tt=(ss=In)+fread(In, 1, 1 << 20, stdin), ss == tt)     \
	? EOF                                                                 \
	: *ss++)
char In[1<<20],*ss=In,*tt=In;
inline int read()
{
	int x=0,c=getchar(),f=0;
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}
inline void write(int x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9)  write(x/10); 
	putchar(x%10+'0');
}

const int N=1e5+5;
int n,k;
int a[N];
int dp[N],dp2[N];

struct Node{
	int l,r,ql,qr;
	// 决策 in [l,r] ，dp数组下标 in [ql,qr];
};
int cnt[N];
queue<Node> q;
int nwl=1,nwr,res;

int calc(int l,int r)
{
	while(nwr<r) res+=cnt[a[++nwr]]++;
	while(nwl>l) res+=cnt[a[--nwl]]++;
	while(nwr>r) res-=--cnt[a[nwr--]];
	while(nwl<l) res-=--cnt[a[nwl++]];
	return res;
}

signed main()
{
	memset(dp,0x3f,sizeof(dp));
	memset(dp2,0x3f,sizeof(dp2));

	dp[0]=0;
	n=read();
	k=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int iiii=1;iiii<=k;iiii++)
	{
		q.push(Node{1,n,1,n});
		while(q.size())
		{
			Node nw=q.front();
			q.pop();
			if(nw.l>nw.r||nw.ql>nw.qr) continue;
			int mid=(nw.ql+nw.qr)>>1,p=0;

			for(int i=nw.l;i<=min(nw.r,mid);i++)
			{
				int to=calc(i,mid)+dp[i-1];
				if(to<dp2[mid]) { dp2[mid]=to,p=i; }
			}
			q.push({nw.l,p,nw.ql,mid-1});
			q.push({p,nw.r,mid+1,nw.qr});
		}
		for(int j=1;j<=n;j++) dp[j]=dp2[j];
		memset(dp2,0x3f,sizeof(dp2));
	}
	cout<<dp[n]<<"\n";
	return 0;
}

CF868F Yet Another Minimization Problem 题解

文章操作

相关推荐

评论

CF868F Yet Another Minimization Problem 题解