粉碎题解

· · 题解

思路

出题人题解。首先思考一个结论，最优的粉碎方案一定是粉碎整个序列的一段前缀，欲证明该结论，只需考虑最后一次粉碎操作即可。如果一对能匹配上的牌分别出现在原序列的 l 和 r 两个位置，则我们可以通过操作把 [1,r] 的牌全粉碎掉。所以，计算最多能粉碎多少张牌，可以转化成求出最后一张可以匹配的牌的位置。

令 dp_i 表示把 [1,i-1] 中所有和 a_i 相等的牌全部粉碎掉的可行性，其中 dp_i=0 表示不可行， dp_i=1 表示可行。令 pre_i 表示上一张和 a_i 相等的牌的位置。注意到，作为更晚出现的牌，i 只有可能和 pre_i 进行匹配，所以 i 是一对可以匹配的牌中更晚被插入的那张，当且仅当 dp_{pre_i}=1。

考虑如何进行转移。dp_i=[pre_i能否在i之前被粉碎]。pre_i 被粉碎有两种方式，一种是与 pre_{pre_i} 匹配，另一种是被 j\in(pre_i,i) ，j 与 pre_j 匹配粉碎掉了。两种方式分别对应以下两种转移：

dp_i|=dp_{pre_{pre_i}} dp_i|=dp_{pre_j},j\in(pre_i,i)

合并一下就是：

dp_i|=dp_{pre_j},j\in[pre_i,i)

此时我们已经得到的 O(n^2) 的做法，优化也是容易的，前缀和优化即可，转移如下：

c_i=c_{i-1}+f_{pre_i} dp_i=[c_{pre_i-1}<c_{i-1}]

于是我们得到了 O(n) 做法。

代码

#include <bits/stdc++.h>
using namespace std;

int a[500010],d[500010],p[500010],c[500010];
bool f[500010];

int main(){
    int t,n,ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);ans=0;
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)
            scanf("%d",a+i),p[i]=d[a[i]],d[a[i]]=i;
        for(int i=1;i<=n;i++){
            f[i]=(c[p[i]-1]<c[i-1]||!p[i]);
            c[i]=c[i-1]+(int)f[p[i]];
            if(f[p[i]])ans=i;
        }
        printf("%d\n",ans);
    }
    return 0;
}