既然秦淮岸没写,那我赶紧抢
本做法为蓝书上做法的刷表版.
设计状态:f[k[0]][k[1]][k[2]][k[3]][k[4]]表示第1行有k[0]人,第二行有k[1]人...的方案数
(即使没有5行,也可以认为没有的那几行应该放0个人,不必分类讨论)
不妨假设加入人是按照编号从大到小加入的,这样就可以保证单调性,于是可得状态转移方程:
$$f[k[0]][k[1]][k[2]][k[3]][k[4]]=\sum…$$
不是因为LATEX坏了,而是因为这样好像写不出来,因为循环枚举行数时没法直接找到其对应的维度
但我还是先强行写一个意会一下:
$$f[k[0]][k[1]][k[2]][k[3]][k[4]]=\sum_{i=0}^{k-1}pre(i)*(k[i]>0,k[i]>k[i+1])$$
$pre(i)$表示第i行比当前状态少放了一个人 的方案数.*(k[i]>0,k[i]>k[i+1])其实就是表示要满足k[i]>0且k[i]>k[i+1]才能选择这种情况(为什么要k[i]>k[i+1]?因为要求每一列上人的编号都是递减的)
这一部分的关键代码如下:
for(k[0]=0;k[0]<=a[0];++k[0])
for(k[1]=0;k[1]<=a[1];++k[1])
for(k[2]=0;k[2]<=a[2];++k[2])
for(k[3]=0;k[3]<=a[3];++k[3])
for(k[4]=0;k[4]<=a[4];++k[4])//很丑的五层循环
{
ll &p = f[k[0]][k[1]][k[2]][k[3]][k[4]];
for (ll j = 0; j < 5; ++j)
if (k[j] > 0 && k[j] > k[j + 1]) {
--k[j];//是的,其实要求得i这一行少放一个人的状态就是这么简单
p += f[k[0]][k[1]][k[2]][k[3]][k[4]];
++k[j];//记得复原
}
}
完整代码就不用了吧.实在要的话点这里
%%%大佬,大佬要不加入Acwing助教群.
现在我还不够强吧,要不过段时间试试?
您实力充足呢.
请问大佬有教学群吗?大家讨论交流的群?很多地方有的题目不是很懂,每次都要看很久QAQ
反对大佬垄断 打破秦淮岸独自贡献题解局面 ! 赞同!!!
秦同学无辜躺枪
QwQ,我好菜的.
+1
目前的题解排序规则很简陋,之后会加以完善,尽量避免时间累积对新题解造成不公平影响。
目前看来y总鸽了/狗头
最近会安排上。
目前看来y总鸽了/狗头
鸽了/狗头 挺久了
看来y总鸽了/狗头 . 进阶指南图论和动规讲解好像 都鸽了