agc013d

71 阅读 0 评论 47 点赞

我是靠谱客的博主超级斑马，最近开发中收集的这篇文章主要介绍agc013d，觉得挺不错的，现在分享给大家，希望可以做个参考。

题目大意

一开始有一个盒子，里面有n个球（黑或白，但是具体的数量我们并不清楚）然后进行m轮这样的操作

1：拿一个球，放到序列中
2：放一个黑球，一个白球
3：拿一个球，放到序列中

问最后的序列的情况数

那么每一次就有00,01,10,11四种情况，并且四种情况都对当前盒子里面的球的数量都有限制
一个困扰我们的问题是一开始盒子里面球的数量是不清楚的，但是发现我们要求的东西和它并没有什么关系，我们关心的只是球的序列

发现对于每一个球的序列对应的合法的初始的白球数量都是一个区间，并且对于这个区间中的最小值一定会卡到一次0

那么考虑dp，设f[i][j][0/1]表示做了i轮，还有j个白球，是否卡到过下界

然后就萎了

发现这样做算漏了没有在任何一轮结束的时候到0，但是在拿了没放的时候卡到0的情况

这样的情况好像只有一种，就是当前只有1个白球并且我们走了01

那么我们第三维状态变成1的情况就变成到过0或者到过1并且在1的时候进行了2操作就好了

本质上就是把任意时刻到达0的情况都计算了一次，这样就不重不漏了

以上就是超级斑马为你收集整理的agc013d的全部内容，希望文章能够帮你解决agc013d所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。