题解：AT_arc195_d [ARC195D] Swap and Erase

· · 题解

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

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

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

#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;
}