文件名称：hdu 3341(ac自动机+状态压缩)
文件大小：23KB
文件格式：WPS
更新时间：2016-11-18 10:49:45
ac自动机
hdu 3341(ac自动机+状态压缩) 题意：容易理解... 思路：首先一开始容易想到要用到dp，开设一个dp[41][41][41][41][501]的数组来解决，但是明显内存已经超出范围了，于是就想如何减少内存呢？只要知道A、T、C、G其中三个的个数，则另一个也能算出，于是空间可以缩小到：41*41*41*500，但是还是不行啊！想了好久还是没找到方法，于是就问了一个大神，他的一个提示给了我灵感：虽然A、T、C、G的个数范围是[0,40]，但是numa+numc+numg+numt的范围也是[0,40]，于是就可以推出numa*numc*numg*numt的范围为[0,15000]（自己写四个for循环可以算出最大为13000多），于是就可以压缩成一个dp[15000][501]的数组了。后来看了网上的方法，他们用了什么变进制，我表示现在还没看懂！！