[deleted]

对，但是对的G

这个G，我击败alksdjfalsdkfjalksdjalsdfa的呵呵呼呼哈哈

先看如果 \(b[]\) 是固定的怎么进行一个算，但是我们可以想到一个的\(dp[i][0/1]\)表示前i位置，，，i位置出平局/胜利手势的最大分数，然后弄一个转移就可以搞:

b[i+1]==(b[i]+1)%3，下一个位置能赢这里，\(dp[i+1][0]=dp[i][0],dp[i+1][1]=\max\{dp[i][0],dp[i][1] \}+1\)
b[i+1]==b[i]，下一个位置跟这里一，样，\(dp[i+1][0]=dp[i][1],dp[i+1][1]=dp[i][0]+1\)
b[i+1]==(b[i]+2)%3，下一个位置输这里，\(dp[i+1][0]=\max\{dp[i][0],dp[i][1]\},dp[i+1][1]=dp[i][1]+1\)

然后那么里面是一个dp呵呵呵呵外面又是dp套dp了[deleted]

令\(f[x][y][z][a]\)表示考虑前x个，有多少种序列能使得\(dp[x][0]=y,dp[x][1]=z\)并且\(b[x]=a\)，如果\(b[x]\)不能是\(a\)，\(f[x][][][a]\)就是0，。考虑下一个位置填什么。，（下面的转移前提是x+1位置可以填对应的值

\(f[x][y][z][a]\to f[x+1][y][\max\{y,z\}+1][(a+1)\%3]\)
\(f[x][y][z][a]\to f[x+1][z][y+1][a]\)
\(f[x][y][z][a]\to f[x+1][\max\{y,z\}][z+1][(a+2)\%3]\)
\(Ans=\sum_{y,z,a}\max\{y,z\}\times f[n][y][z][a]\)

呵呵转移倒好是O(1)但是状态是\(O(n^3)\)，[deleted]没救[deleted]

现在出题人有神奇观察：不关心\(x,y\)，只关心\(x-y\)，答案提前累加，什磨意，思呢？？、、、、

重新定义\(f\)令\(f[x][d][a]\)表示上面的的\(\sum_{y,z,y-z=d}f[x][y][z][a]\)。这样好的，可以转移\(f\)但是爆笑答案求不了

于是在定义\(g[x][d][a]\)表示原来的\(\sum_{y,z,y-z=d}\max\{y,z\}\times f[x][y][z][a]\)。惊讶的发现，[deleted]可以算

这公式我真的敲不动了，反正代码也很短而且我代码里的变量含义跟题解一摸一样我就粘呵呵呵呵，，，

for(int i=1;i<n;i++){
    for(int j=-n;j<=n;j++){
        for(int a=0;a<3;a++){
            int nj;
            //a->a+1
            if(b[i+1]==(a+1)%3||b[i+1]==-1){
                if(j>=0)nj=-1;
                else nj=j-1;
                addto(f[i+1][maxn+nj][(a+1)%3],f[i][maxn+j][a]);
                addto(g[i+1][maxn+nj][(a+1)%3],add(g[i][maxn+j][a],f[i][maxn+j][a]));
            }
            //a->a
            if(b[i+1]==a||b[i+1]==-1){
                nj=-j-1;
                if(j>=0)
                    addto(f[i+1][maxn+nj][a],f[i][maxn+j][a]),
                addto(g[i+1][maxn+nj][a],add(g[i][maxn+j][a],f[i][maxn+j][a]));
                else
                    addto(f[i+1][maxn+nj][a],f[i][maxn+j][a]),
                addto(g[i+1][maxn+nj][a],g[i][maxn+j][a]);
            }
            //a->a-1
            if(b[i+1]==(a+2)%3||b[i+1]==-1){
                if(j>0)
                    nj=j-1,
                addto(f[i+1][maxn+nj][(a+2)%3],f[i][maxn+j][a]),
                addto(g[i+1][maxn+nj][(a+2)%3],g[i][maxn+j][a]);
                else
                    nj=-1,
                addto(f[i+1][maxn+nj][(a+2)%3],f[i][maxn+j][a]),
                addto(g[i+1][maxn+nj][(a+2)%3],add(g[i][maxn+j][a],f[i][maxn+j][a]));
            }
        }
    }
}

答案\(\sum g[n][][0/1/2]\)

THC

2024 Nowcoder Round 8 Tutorial

[deleted]

对，但是对的G