又是一道神DP 还是太弱了 不会搞 PR给了一个100*100*50*50*100的算法 后来看别人的100*50^4没看懂 最后Fu点醒了我

先说的PR的方法 . . . . . . . . . . . 显然good array 必然是类似山峰状的一个东西 可以像搭房子一样从下到上一层一层的往上搭 ? ? . . . . . . . 将{bi}看做一个数字序列，比如将222223333445555666看做5,4,2,4,3（相同数的个数）,记作{ci} ans=1 A=c1 for(i=2;i<=|ci|;i++) { B=ci; ans*=C(B-1,A-1); //如果A==0或A>B这条式子本身就不成立，式子中已经包含了无解的条件 A=B-A; } f[i][j][k][s] 表示现在这一层的数是i（你可能从2,3,4...开始"建房子",地基的位置是由{bi}中的最小值决定的）， 已经用掉（包括当前最小点）j个点， 总方案数为k， 当前这一层有s(就是上面伪代码中的A)段的方案数 -> (枚举第i+1层要放l个点(即上面伪代码中的B)) f[i+1][j+l][k*C(l-1,s-1)][l-s] (l > s)

显然 i l 是<=n/2 k j<=n 转移是 N 所以是 100^3*50^2 // 题解的方法更加神

题解的大致思路和上面相同 但是在设计状态的时候却更加巧妙 f[i][count][lastnumber][way] 用了前i个数 一共有 count个数 上一个数用了lastnumber次 有k种方法弄good way

注意巧妙的用了 上一个数用了lastnumber次 那么在这次转移中 如果我们要加入y个i+1但是 一个i+1 的周围肯定是两个i所以要再加一个i+1 必须要加一个i 来套住他 由于原来的i不会有相邻的所以这样总是可行的方案。 然后算新的方案： 就是对于原来的每个i,我可以添加 ai个i+1 那就是 a1+a2+..+ax=y 非负整数解的个数就是 C(x+y-1,x-1)=C(x+y-1,y) (隔板法) f[i][count+2*y][y][nowway]+=f[i][count][lastnumber][way] 又由于每次count加的都是2的倍数 所以第二维 和转移也都变成了 n/2 所以是 100*50^4