5248: [2018多省省队联测]一双木棋

容易写出暴力.
c++代码如下:

上述代码50分.
考虑如何优化
发现其实每一层当前能选的都是固定的.
那么考虑状压来表示出每一层的状态.
因为m最大为10,根据题意显然总变化不会超过10
用1表示向左边移动,0表示该层结束
那么可以用f[i][j]表示第一层从i开始,接下来状态为j
比如i = 5,j = 111010(2进制)
表示第一层为5 ,第二层为5,第三层为4,第五层为1,接下来的层均为1.
那么这样表示发现状态一定不会超过2^20
然后考虑转移即可。
c++代码如下:

 

1 + 7 =