题解：P12264 『STA - R9』咏叹调调律

· · 题解

update：应 jijidawang 要求在末尾换成了一份调试版代码

可能是内测人员题解。

这个题场上很多选手都写了假的 dp，获得了 35 分，事实上当初验这个题的时候大家都写假 dp 爆炸了，然后前面 5 分暴力的包其实能起到一个提示你假了的作用，然后这个题拥有一份正确的指数暴力是非常重要的，然而场上并没有很多人去写这个暴力，我们几个翻提交记录的时候一起变身急急大王。

首先子串的可删性是不好刻画的，首先看一下特征，就是 \text{B} 全在结尾，\text{C} 全在开头，那么如果只有 \text{B} 和 \text{C} 就只有 \text{CCB} 一种消除方式，考虑一个括号序列，左括号匹配一个右括号，这里两个 \text{CC} 匹配一个 \text{B}，就是 \text{C} 是左括号，\text{B} 是两个右括号。

那么我们发现 \text{A}，相当于是选择成为两个左括号或者一个右括号。

现在考虑简单情况，就是一个括号序列，可以填写 \text{(},\text{?},\text{)}，其中问号代表通配符，问合法的括号序列的个数。

发现如果一个序列合法的话必然将一个前缀的问号全换成左括号，后缀全部换成右括号不劣，并且这样合法的分界点只有一个，设 dp_{i,j,0/1} 表示填到第 i 个数，前面剩下 j 个没匹配的左括号，当前的问号代表 左/右 括号，直接做就好了（事实上这题已经能做1e7了，灌注 jijidawang 谢谢喵，灌注 joke3579 谢谢喵）。

接下来考虑原问题，这个 \text{A} 就是刚才的问号的地位，接下来所有特殊性质就显然了。

然后有一个深刻的问题就是 \text{AACB} 转化成括号之后是 \text{(()())}，但是它消不掉，这里需要特殊注意一下，因为后面的 \text{B} 不能拆成一半和前面的 \text{AA} 匹配，一半和前面的 \text{C} 匹配。

那么我们仿照上面的括号处理方式，先来考虑如何判定：

  1. 每当遇到一个单独的右括号的时候肯定优先匹配双左括号，注意剩下的这一个括号是特殊的（只能用 \text{A} 也就是单右括号删除,但是可以被 \text{B} 抢夺）。

  2. 每当遇到一个双右括号的时候优先匹配双左括号，否则的话匹配两个单左括号。

于是设 dp_{i,j,k,s,0/1} 表示到第 i 个数，前面有 j 个单左括号，k 个双左括号，特殊括号的状态，当前问号的状态。

直接 dp 就好了，代码非常难看。

提供一份调试用代码，输入 n，它会按照字典序输出所有长为 n 的咏叹调，大概能跑 n \le 15。

它实现和正解的 dp 几乎没区别，就是把答案集合全部记录了，一些实现细节也可以看里面的。

#include<bits/stdc++.h>
using namespace std;
using llt=long long;
const llt N=20,mod=998244353;
llt n;vector<string> dp[N][N][N][3][2],Ans;
void add(vector<string> &S,vector<string> A,char s){if(s=='O')for(auto v:A)   S.push_back(v);else for(auto v:A)   S.push_back(v+s);}
int main()
{
    cin>>n;
    dp[0][0][0][0][0].push_back("");
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
            for(int k=0;k+j<=i;k++)
            {
                if(j>=1)
                    add(dp[i][j][k][0][0],dp[i-1][j-1][k][0][0],'A'),
                    add(dp[i][j][k][1][0],dp[i-1][j-1][k][1][0],'A'),
                    add(dp[i][j][k][2][0],dp[i-1][j-1][k][2][0],'A');
                add(dp[i][j][k][(k>0)+1][1],dp[i-1][j+1][k][0][1],'A');
                add(dp[i][j][k][(k>0)+1][1],dp[i-1][j+1][k][0][0],'A');
                add(dp[i][j][k][0][1],dp[i-1][j][k][1][1],'A');  
                add(dp[i][j][k][0][1],dp[i-1][j][k][2][1],'A');  
                add(dp[i][j][k][0][0],dp[i-1][j+1][k][0][0],'B'),
                add(dp[i][j][k][0][1],dp[i-1][j+1][k][0][1],'B'),
                add(dp[i][j][k][1][0],dp[i-1][j+1][k][1][0],'B'),
                add(dp[i][j][k][1][1],dp[i-1][j+1][k][1][1],'B'),
                add(dp[i][j][k][2][0],dp[i-1][j+1][k][2][0],'B'),
                add(dp[i][j][k][2][1],dp[i-1][j+1][k][2][1],'B');
                if(k>=1)
                    add(dp[i][j][k][0][0],dp[i-1][j][k-1][0][0],'C'),
                    add(dp[i][j][k][0][1],dp[i-1][j][k-1][0][1],'C'),
                    add(dp[i][j][k][1][0],dp[i-1][j][k-1][1][0],'C'),
                    add(dp[i][j][k][1][1],dp[i-1][j][k-1][1][1],'C'),
                    add(dp[i][j][k][2][0],dp[i-1][j][k-1][2][0],'C'),
                    add(dp[i][j][k][2][1],dp[i-1][j][k-1][2][1],'C');
            }
        for(int k=0;k<=i;k++) 
            add(dp[i][0][k][0][0],dp[i-1][0][k+2][0][0],'B'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+2][0][1],'B'),
            add(dp[i][0][k][1][0],dp[i-1][0][k+2][1][0],'B'),
            add(dp[i][0][k][1][1],dp[i-1][0][k+2][1][1],'B'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][0][0],'A'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][0][1],'A'),
            add(dp[i][0][k][0][1],dp[i-1][0][k+1][2][1],'B');
        for(int j=0;j<=i;j++)   add(dp[i][j][0][1][1],dp[i][j][0][2][1],'O');
    }
    add(Ans,dp[n][0][0][0][0],'O');add(Ans,dp[n][0][0][0][1],'O');sort(Ans.begin(),Ans.end());
    for(auto v:Ans) cout<<v<<endl;
    return 0;
}