题解：P14256 平局（draw）

· · 题解

T4 又是神秘计数题，做疑难 dp 时可以先分析子问题将其转化，进而解决大问题。先考虑这个问题：对于一个给定的序列，如何求解最大平局问题？

显然，先将相同的一堆串合并，再接着考虑。我们用 0 -1\hspace{0.1cm} 1 分别代表平、胜、负。那原序列就转化成了一个只有 \pm1 的序列，然后发现合并操作就是将不同的变成 0，相同的取相反数（手玩即可）。那就有一个策略：先将能取的 0 都取了，然后尽可能将 1 和 -1 合并成 0，我们就可以开一个栈，显然任意时刻栈里只会有一种元素，那么容易发现，三个相同的元素可以直接合成出一个 0。为了方便后续解决问题，我们钦定栈里的元素应该都是 1,那么发现当且仅当栈里只有一个元素时，其可能为 -1（有两个 -1 时直接合成一个 1 一定不劣，显然易证）。之后按照上述方式合成一定是最优的。

想到这就可以完成前 6 个数据点了，复杂度 O(n3^n)。

接下来进一步想正解，我们发现上述过程中有用的信息只有两个：栈里 1 的个数与是否有 -1。于是可以自然的设出状态： f_{i,j,0/1,0/1/2} 表示前 i 个人中栈里有 j 个 1 ，是否有 -1，结尾是石头/剪刀/布时的方案数与贡献（这两个分开记是因为有的状态会合成出 0 造成贡献，有的状态会使方案更多而不会使答案更多）。

那么转移就需要一些分类讨论，直接看代码吧。

for(int j=0;j<3;j++) if(s[1]>>j&1) f[1][0][0][j].F=1;
    for(int i=2;i<=n;i++) for(int j=0;j<i-1;j++) for(int p=0;p<2;p++) for(int k=0;k<3;k++){
        Pa w=f[i-1][j][p][k];
        for(int o=0;o<3;o++) if(1<<o&s[i]){
            int b=(k-o+4)%3-1;
            if(b==0) add(f[i][j][p][o],{w.F,(w.F+w.S)%P});//相同了，这样转移是因为它对每种方案都会贡献1，所以贡献加上方案数*1，下面同理
            else if(!j&&!p){//栈空 
                if(b==1) add(f[i][1][0][o],w); 
                else add(f[i][0][1][o],w);
            }else if(b==1) add(f[i][j+1][p][o],w);//赢了 
            else{
                if(j) add(f[i][j-1][p][o],{w.F,(w.F+w.S)%P});//输和赢拼一个0
                else add(f[i][1][0][o],w);//用两个输拼一个赢 
            }
        }
    }
    for(int i=0;i<n;i++) for(int j=0;j<2;j++) for(int k=0;k<3;k++)
            (ans+=(f[n][i][j][k].S+1ll*f[n][i][j][k].F*(i/3)%P)%P)%=P;

这道题其实说明一个想 dp 的方法：先想出一个正确且有前途的求解子问题的方法，观察此过程中记录的变量，将其当状态进行 dp。