题解：AT_arc195_d [ARC195D] Swap and Erase

感性证明一下每个数最多只会被换一次的结论。

我们考虑怎样交换才是优的，举个栗子：

CPP

A B A B

显然交换中间的 A 和 B 才是优的。

所以说我们得到一个结论：只有在交换后，

2

操作的数量减两次及以上才会更优，但一次操作最多减两次，所以交换后，

2

操作的数量减两次才会更优。

我们考虑对于同一个数，交换两次会发生什么。

那么就是说，你一共要减少四次

2

操作，才能使交换两次比交换两次以下更优。

但是我们又发现，你对于同一个数交换两次，最多只会影响三个数，也就是说最多只会减少三个

2

操作，所以显然是不优的。

那么交换两次已经是不优的了，那么交换两次以上也是不优的了。

所以每个数最多只会被交换一次。

如果有了这个结论，剩下的就很简单了。

设

f_{i,0/1}

表示对于序列

a_1,a_2,\dots,a_i

，将

a_i

与

a_{i-1}

不换/换时，最少要几次操作才能将序列清空。

然后就可以列出 dp 方程：

\begin{cases} f_{i,0}=\min(f_{i-1,0}+[a_i\not =a_{i-1}],f_{i-1,1}+[a_i\not=a_{i-2}])\\ f_{i,1}=1+[a_i\not=a_{i-1}]+\min(f_{i-2,0}+[a_i\not=a_{i-2}],f_{i-2,1}+[a_i\not=a_{i-3}]) \end{cases}

~~所以楼上 dp 方程似乎错了？~~

code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int mod=998244353;
int n,m,a[N],ans;
int f[N][2];
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	f[1][0]=1,f[1][1]=mod;
	for(int i=2;i<=n;i++){
		f[i][0]=min(f[i-1][0]+(a[i]!=a[i-1]),f[i-1][1]+(a[i]!=a[i-2]));
		f[i][1]=1+(a[i]!=a[i-1])+f[i-2][0]+(a[i]!=a[i-2]);
		if(i>2) f[i][1]=min(f[i][1],1+(a[i]!=a[i-1])+f[i-2][1]+(a[i]!=a[i-3]));
	}
	cout<<min(f[n][0],f[n][1])<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int _;
	cin>>_;
	while(_--) solve();
	return 0;
}

题解：AT_arc195_d [ARC195D] Swap and Erase

文章操作

code

相关推荐

评论

题解：AT_arc195_d [ARC195D] Swap and Erase