本文介绍: 这个时候我们再考虑下以一个下标为结尾的话能不能优化出来,发现前一个下标状态的方案数可以转移到当前下标的状态的方案数,是有一个规律,比如1 2 3,第四个数是4,前三个的方案数是6,那么转移到第四个的话,总共方案数是多少呢?那么本题中就多了一个条件就是一定要是0,1,2序列才行,那么我们转移时是0,1,2的时候判断一下就行了,比如当前位是1,那么只能从前面结尾是0的序列,和前面有个结尾是1的序列转移过来,两个相加。f[i][1],f[i][2]这个状态怎么办呢?
本题中不同特殊子序列其实就是组成子序列(不一定要连续的),只不过这题还加入了限制,就是子序列必定满足0,1,2这个顺序的而已。
那么这题我们先想一个暴力解法,就是怎么样才能把所有序列都统计进去,其实在考虑这道题的暴力解法之前,我们把他看做一个不用满足0,1,2这个顺序的序列,随便组的话,是不是n^3了,从一个作为为起始点地方延伸出去的情况下。这个时候我们再考虑下以一个下标为结尾的话能不能优化出来,发现前一个下标状态的方案数可以转移到当前下标的状态的方案数,是有一个规律,比如1 2 3,第四个数是4,前三个的方案数是6,那么转移到第四个的话,总共方案数是多少呢?以第一个数为结尾的方案数有1,前二个数结尾的方案数等于以第一个结尾的方案数加上以第二个为结尾的方案数1 + 1 + 1等于3,前三个为结尾的有3 + 3等于6。那么本题中就多了一个条件就是一定要是0,1,2序列才行,那么我们转移时是0,1,2的时候判断一下就行了,比如当前位是1,那么只能从前面结尾是0的序列,和前面有个结尾是1的序列转移过来,两个相加
f[i][1] = f[i – 1][0] + f[i – 1][1] + f[i – 1][1];同理当前位是2也是,同理当前位为1也是,但是这里还有一个很重要的点就是,这个数是0的时候,其他的状态怎么办呢?f[i][1],f[i][2]这个状态怎么办呢?
这个我们就之前转移前面的,因为我们在转移的时候,只要知道当前位之前的序列方案数就行,那么这样其实我们就可以优化了,只用三个数就可以知道了,一个数保存前i个状态的0序列总的方案个数,同理,这里我就不优化了
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。