题解：B4323 [科大国创杯小学组 2025] 改写

XZhuRen · 2025-04-21 18:13:17 · 题解

@JHPOTATO 大神出的题目，快去膜拜她 qwq。

考虑乱搞。

发现同段一定是回文取不到，两段接一起必然不回文可以取，把段长缩小到 \min(len,2)。

长度由 \mathcal{O}(\sum len) 压缩到了 \mathcal{O}(m)。

直接写出串，感性理解，回文长度一定不超过 5，DP 一个最大值 f_i 表示压缩后的串前 i 个字符的答案，暴力往前做 4 次转移即可。

官方题解划分等价类严谨证明，下面感性证一下：

已经将长度缩到了 2 以内，连续两段长度和不超过 4，转移最优下不会多取。

注意到 m=3 的情况可能需要特判第一段长度等于第二段，这个取决于实现。

代码：

int n,m;
int a[400005];
int dp[400005];

bool checkpl(int l,int r) {
    for(int i=l;i<r+l-i;++i) {
        if(a[i]!=a[r+l-i]) return false;
    }
    return true;
}

void wk() {
    read(m);n=0;
    if(m==3){
        char x[4];
        int y[4];
        for(int i=1;i<=m;i++){
            cin>>x[i]>>y[i];
        }
        if(x[1]==x[3]&&y[1]==y[3]&&y[2]==1)printf("-1\n");
        else if(y[2]==1)printf("1\n");
        else printf("2\n");
        return;
    }
    char x;int y;
    for(int i=1;i<=m;++i) {
        cin>>x>>y;
        (x-='a')+=1;
        y=min(y,2);
        while(y--) a[++n]=x;
    }
    for(int i=1;i<=n;++i) dp[i]=-1e9;
    for(int i=1;i<=n;++i) {
        for(int j=i;i-j<=4 && j>=1;--j) {
            if(!checkpl(j,i)) dp[i]=max(dp[i],dp[j-1]+1);
        }
    }
    if(!checkpl(1,n)) dp[n]=max(dp[n],1);
    writeln(dp[n]<0?-1:dp[n]);
}