自动搬运

查看原文

来自洛谷，原作者为

	sdyzpf 不卖了

搬运于2025-08-24 23:03:28，当前版本为作者最后更新于2024-08-29 15:28:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

出题人题解。首先思考一个结论，最优的粉碎方案一定是粉碎整个序列的一段前缀，欲证明该结论，只需考虑最后一次粉碎操作即可。如果一对能匹配上的牌分别出现在原序列的 $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$ 匹配粉碎掉了。两种方式分别对应以下两种转移：

合并一下就是：

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

于是我们得到了 $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;
}