在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
这一题我是想不出来, 但是我想吐槽一下坐我左边的大佬。 大佬做题的时候,只是想了几分钟,拍了拍大腿,干脆的道:“这不是很显然吗!” 然后灵动地轻击键盘,不时抚弄头发,光速切紫题。 AC后笑眯眯地对我说, 你要是想的出来,我给你买一瓶2L可口可乐! 我当然难以下手,但2L杀***水非常诱惑。 还是冥思苦想了一番, 大佬看着着急,就告诉了我状态定义,还笑着说,告诉你你也想不出方程。 我很生气,但身为蒟蒻又能怎样呢? 在大佬的不断提示下,我勉强把这题做了出来。 讲讲怎么做吧~ 先看这题怎么样才算无解呢, 假设\(cnt[i]\)表示\(m\)个人中编号\(\ge i\)的个数。显然当\(cnt[i]>=n-i+1\)时无解。 大佬叫我这样定义状态\(f[i][j]\)表示剩下\(n-m\)个人中编号\(\ge i\)的人有\(j\)个。 所以,我们这么转移\(f[i][j]+=f[i+1][j-k]*C_{j}^{k}\)。 表示我们此时已经选了\(j-k\)人,再选\(k\)人的方案数。 注意事项: 因为方程是从\(i+1\)转移过来的,所以我们的\(i\)要倒过来枚举,答案显然是\(f[1][n-m]\)。 复杂度显然\(O(n^3)\),当然还要乘上数据组数。 上代码~
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论