【NOIP2015】子串

这道题乍一看好像是字符串,仔细想想就会发现是个dp问题。

用d[i][j][k]表示A串中分出k块,最后一块以第i个数为结尾,匹配完B串种j位的方案数。

则可以得到

d[i][j][k]=(a[i]==b[j])*( +(a[i-1]==b[j-1]&&j>k)*d[i-1][j-1][k];

即当a[i]不等于b[j]时d[i][j][k]=0,前半部分表示i单独作为一块时的方案数,后半部分表示若a[i-1]==b[j-1]并且j>k(保证j-1能分为k块)时将i接在i-1后面的方案数。

每次求和导致复杂度过高,所以可以新开一个数组,维护前缀和。

可以发现数据正好会爆空间,所以还要使用滚动数组。

时间复杂度O(nmk)。

说点什么

  Subscribe  
提醒