题解：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

造成贡献，有的状态会使方案更多而不会使答案更多）。

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

CPP

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。

题解：P14256 平局（draw）

文章操作

相关推荐

评论

题解：P14256 平局（draw）