题意

给出一个长度为

n

的序列

a

。

还有一个初始为

0

的数组

c

。

可以执行以下操作任意次：

选择三个元素 $i$ , $j$ 和 $k$ （ $1 \leq i < j < k \leq n$ ）。

条件： $c_i=c_j=c_k=0$ 且 $a_i=a_k$ 。

效果： $c_j=1$ 。

求操作后

\sum\limits_{i=1}^n{c_i}

的最大值。

做法

一眼 DP。

设 $f_i$ 表示区间 $1$ 到 $i$ 的没有贡献的数的个数， $lst_i$ 表示元素 $i$ 第一次在 $a_i$ 中的下标。

初始化，

f_1=1

，因为第一个怎么操作都不可能有贡献。

对于每一个

i

，他可以把

lst_{a_i}+1

到

i-1

赋值，我们枚举

j

，其中

\min(lst_{a_i},i-1)\leq j \leq i-1

，考虑将

j+1

到

i-1

赋值。所以

f_i=f_j+1

，这个

+1

是算上

i

本身无法赋值。

那么 DP 方程式也就呼之欲出：

$f_i=\min\limits_{j=\min(lst_{a_i},i-1)}^{i-1}f_j+1$

可这

n^2

的时间复杂度肯定过不了，用个线段树维护一下区间最小值就行了。

~~做蓝题的人应该没有不会线段树吧。~~

但是，有人要问了，如果

lst_{a_i}

的

c

为

1

你都不知道那不是出锅了吗。

表面上来看，这样的问题确实存在，看似不可做，但仔细一想就可发发现，你总能改变赋值顺序来做到理想的贡献（手模几个样例理解更深）。

Code

CPP

#include<bits/stdc++.h>
#define ls(a) a<<1
#define rs(a) a<<1|1
using namespace std;
const int MAXN=1e6+10;
const int INF=1e9+7;
int n,g,a[MAXN],tree[MAXN],lst[MAXN];
//----------------线段树板子（求最小值）------------- 
void push_up(int x){
	tree[x]=min(tree[rs(x)],tree[ls(x)]);
}
void build(int x,int l,int r){
	if(l==r){
		tree[x]=INF;
		return;
	} 
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	push_up(x);
}
void update(int ql,int qr,int l,int r,int x,int k){
    if(ql<=l&&r<=qr){
    	tree[x]=min(tree[x],k);
        return ;
    }
    int mid=(l+r)>>1;
    if(ql<=mid) update(ql,qr,l,mid,ls(x),k);
    if(qr>mid) update(ql,qr,mid+1,r,rs(x),k);
    push_up(x);
}
int query(int ql,int qr,int l,int r,int x){
    int ans=INF;
    if(ql<=l&&r<=qr) return tree[x];
    int mid=(l+r)>>1;
    if(ql<=mid) ans=min(ans,query(ql,qr,l,mid,ls(x)));
    if(qr>mid) ans=min(ans,query(ql,qr,mid+1,r,rs(x)));
    return ans;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=n;i>=1;i--) lst[a[i]]=i;
	build(1,1,n),update(1,1,1,n,1,1);//初始化，第一个肯定没贡献 
	for(int i=2;i<=n;i++) g=query(min(lst[a[i]],i-1),i-1,1,n,1)+1,update(i,i,1,n,1,g);
	//DP
	printf("%d",n-g);//答案为：总的-没贡献的 
	return 0;
}

题解：CF1630C Paint the Middle

文章操作

题意

做法

Code

完结散花

相关推荐

评论

题解：CF1630C Paint the Middle