竞赛讨论区 > 【每日一题】5月29日题目精讲
头像
王清楚
编辑于 2020-05-29 14:33
+ 关注

【每日一题】5月29日题目精讲

题号 NC17621
名称 管道取珠
来源 NOI2009比赛真题
戳我进入往期每日一题汇总贴~
往期每日一题题单
图片说明
如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

这个题的难点或者说关键点究竟在哪里呢?
——弄清楚究竟是什么意思!因为是肯定不能直接算的!(我们考虑把数学式子弄出一个物理意义或者说实际操作的意义)
表示:如果有两个相同的装置同时进行取珠子的操作,两个装置取得相同的序列的方案数有多少。
想想哈:ai是组成第i个序列的方案数,那么 是两个装置都取得第i个序列的方案数是理所当然的哈!
这样就简单了,f[i][j][k] 表示已经取了i个珠子,第一个装置第一行取了j个,第二个
装置第一行取了k个,所得到的序列是一样的的方案数,转移方程显而易见, 注意,由于空间限制要01滚动的……
转移方程如下:
if (j > 0 && k > 0 && a[j] == a[k]) f[i%2][j][k] += f[(i-1)%2][j-1][k-1];
if (b[i-j] == b[i-k]) f[i%2][j][k] += f[(i-1)%2][j][k];
if (j > 0 && a[j] == b[i-k]) f[i%2][j][k] += f[(i-1)%2][j-1][k];
if (k > 0 && b[i-j] == a[k]) f[i%2][j][k] += f[(i-1)%2][j][k-1];
(这种思路在当年noi之后就成为了套路……但是第一次见真的很难想到。)



欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目6月5日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(17) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐