HDU 5745 La Vie en rose（DP+bitset优化） DP

[题目链接]
[题意]
给定模式串和主串，模式串可以交换相邻位子的字符，且可以交换多个位子，但每个字符只能被交换一次。问模式串能否通过该变换与主串匹配？输出主串中每个位子的匹配结果，1为可匹配，0为不可匹配。
[分析]
赛上被这道题坑哭了，看到那么多队过自己却没有思路，好不容易想到个方法把样例过了却T了。最后走投无路写了个暴力就A了，1500ms，吓死。
不过赛后貌似加强了数据，卡了暴力，丧病。
不过趁机学习了下bitset优化的方法，还不错
dp公式很容易得到
设主串为s，模式串为t，dp[i][j][k]表示主串到i，模式串到j，模式串当前位置的状态为k（0：不动，1：与前面交换，2：与后面交换）是否匹配，则：
dp[i][j][0] = （dp[i-1][j-1][0] || dp[i-1][j-1][1] ） && （s[i] == t[j]）
dp[i][j][1] = （dp[i-1][j-1][2] ) && ( s[i-1] == t[j] )
dp[i][j][2] = （dp[i-1][j-1][0] || dp[i-1][j-1][1] ）&& （s[i+1] == t[j] )
优化1：
第二维j实际上只与j-1有关，可以滚动
优化2：
所有值都是bool类型，可以用bitset压位，通过bitset之间的位运算，常数优化
其实听了这些对不会玩bitset的来说还是一脸懵逼（比如我
所以具体一点吧

bitset dp[2][3] , ch[26] ;

首先需要这些bitset，前者当然是存dp值，2用于滚动，3存三种状态；后者对应26个字母是否在主串中的某个位子出现，比如ch[0][5]表示字母a是否出现在主串中的第5个位子

dp[cur][1] = (dp[cur^1][2] << 1) & ch[t[i-1]-'a'] ;

转移的时候这样搞，这里只列出了k=1的转移写法
由于两个bitset可以直接进行位运算，相当于一次运算直接把1-n的所有dp值全部算出，复杂度却只有O(n/w)（w是机器的字节长）
所以预处理每个字符是否在每个位子出现，保存在bitset中，就是为了这里的操作
还有一个疑问，为何要<<1?
很简单，因为i由i-1推得，所以左移1使得对应的位对齐，再运算
这样写刚好卡过
【HDU 5745 La Vie en rose（DP+bitset优化）】[代码]

#include using namespace std ; const int N = 100000 + 5 ; typedef long long LL ; int T , n , m ; char s[N] , t[N] ; bitset dp[2][3] , ch[26] ; int main() { scanf( "%d" , &T ) ; while( T-- ) { scanf( "%d%d" , &n , &m ) ; scanf( "%s%s" , s+1 , t+1 ) ; for( int i = 0 ; i < 26 ; i++ ) ch[i].reset() ; for( int i = 1 ; i <= n ; i++ ) ch[s[i]-'a'].set(i) ; int cur = 0 ; dp[cur][0].set() ; dp[cur][1].reset() ; dp[cur][2].reset() ; for( int i = 1 ; i <= m ; i++ ) { cur ^= 1 ; for( int j = 0 ; j < 3 ; j++ ) dp[cur][j].reset() ; dp[cur][0] = ((dp[cur^1][0] | dp[cur^1][1]) << 1) & ch[t[i]-'a'] ; if( i > 1 ) dp[cur][1] = (dp[cur^1][2] << 1) & ch[t[i-1]-'a'] ; if( i < m ) dp[cur][2] = ((dp[cur^1][1] | dp[cur^1][0]) << 1) & ch[t[i+1]-'a'] ; } for( int i = m ; i <= n ; i++ ) s[i-m] = '0' + (dp[cur][0][i] | dp[cur][1][i]) ; for( int i = n-m+1 ; i < n ; i++ ) s[i] = '0' ; s[n] = 0 ; puts(s) ; } return 0 ; }