2019牛客多校第一场E – ABBA

题目链接:2019牛客多校第一场E

题意是一共有$n+m$个$A$,$n+m$个$B$,要组成一个可以拆分成$n+m$个子序列的字符串,其中有$n$个$AB$,$m$个$BA$,问有多少种。

贪心地考虑,前面的$A$优先给$AB$中的$B$匹配,前面的$B$优先给$BA$中的$A$匹配,因为如果前面的$A$优先给$BA$使用,不利于后面的$B$匹配$BA$。

我们用$f(i,j)$来表示$i$个$A$和$j$个$B$在这种贪心策略下的组成个数,转移的时候依次枚举是放$A$还是放$B$(这里指的是加到原序列的后面)。那么只有$i$不比$j$多$n$个的时候才能放$A$,即$f(i,j)$可以转移到$f(i+1,j)$(这里也可以细分,$i$比$j$少的时候和$i \geq j$并且$i – j < n$);同样地,只有$j$不比$i$多$m$个的时候才能放$B$,即$f(i,j)$可以转移到$f(i,j+1)$。

渐进时间复杂度$O((n+m)^2)$。

 

 

说点什么

avatar
50
  Subscribe  
提醒