首页 > 代码库 > HDOJ多校联合第四场

HDOJ多校联合第四场

B题:

 

C题:仅由‘A‘,‘G‘,‘C‘,‘T‘,4个字母组成,给定一个字符串S,|S|<=15,给定一个整数m,以m为长度且仅含4种字母的字符串T,求LCS(S,T)为0,1,2,3....|S|,时相应字符串T的数目。

分析:dp+状态压缩

反正我不会这题,也是看了羊神的代码之后才明白这题的思路

下面说说我的理解吧:

 

由于|S|长度最大为15,所以用一个二进制编码表示是哪些位置上的字母构成LCS,并求相应的数目。

dp[0][st],dp[1][st]记录的是相应字母构成LCS时,T可能的数目,然后一个一个去给T添加字母直到T长度为m。注意先要将某种状态st添加某个字母后变化成另一种状态的转移处理出来。

now[i]表示S中前i个字母和T的LCS长度,添加一个字母后用数组next[i]记录,表示S前i个字母和添加一个字母的T的LCS长度。

预处理时转移方程就是:

 

next[i] = now[i-1]+1(s[i-1] == da[k])

next[i] = max(next[i-1], now[i]) (s[i-1] != da[k])

这个转移和一般求两个字符串LCS是相同的。

然后就是根据处理出来的转移,一个一个添加字母并且记录数目:

dp[0][st] 添加字母c到达状态st‘,则此时可能的字符串数目dp[1][st‘]需要加上前面未添加字母时那部分的数目:

dp[1]st‘] += dp[0][st];

代码:

View Code