这道题的$64pts$很好拿。

瞎写两个背包就好了。

考虑$88pts$做法,

如果计算总方案数,应该对于在座来说不难

有$s_i=\sum a_{i,j}$,对于$g_{i,j}$,即前$i$层选$j$个,应该有

$g_{i,j}=g_{i-1,j}+g_{i-1,j-1}*s_i$

总方案数就为$\sum g_{n,j}$

困难就困难在如何排除不合法的方案。

根据题意的描述,

只要有(也只有一种)超出$\left\lfloor{k/2}\right\rfloor$个,就是不合法的。

可以考虑设计出一个状态$f_{i,j,k}$表示前$i$行,$col$列选了$j$个,其他列选了$k$个。

清楚了定义之后,不合法的就是$\sum_{j>k} f_{n,j,k}$

转移方程:$f_{i,j,k}=f_{i-1,j+1,k}*a_{i,col}+f_{i-1,j,k}+f_{i-1,j,k+1}*(s_{i}-a_{i,col})$

$100pts$做法建立在$j>k$这个条件下,

因此$j-k>0$即不合法,因此是一个相对概念,压掉一维。

$f_{i,j}$即可。

相应转移方程就为$f_{i,j}=f_{i-1,j+1}*a_{i,col}+f_{i-1,j}+f_{i-1,j-1}*(s_i-a_{i,col})$