Codechef STREDUC Reduce string Trie、bitset、区间DP

VJ传送门

简化题意：给出一个长度为\(l\)的模板串\(s\)与若干匹配串\(p_i\)，每一次你可以选择\(s\)中的一个出现在集合\(\{p_i\}\)中的子串将其消去，其左右分成的两个串拼接在一起形成新的串\(s\)。问如是进行消除，最后\(s\)的最短长度。

当时没想到做法，现在看起来还是比较简单欸……

考虑计算出所有可以被消除的区间然后\(DP\)

先将所有匹配串插入到Trie树上，设\(f_{i,j,k}\)表示子串\(s_{i,j}\)通过任意消除得到的串是否能对应到\(Trie\)树的\(k\)号节点上。转移分两种：

①在子串\(s_{i,j-1}\)之后接上\(s_j\)，直接在\(Trie\)树上找是否存在对应的儿子；②存在某个子串\(s_{x,j}(x > i)\)可以被消除，那么\(\forall k, f_{i,j,k} |= f_{i,x-1,k}\)

计算完成后，如果存在\(k\)使得某一个匹配串在\(Trie\)树上对应节点\(k\)且\(f_{i,j,k}=1\)，那么意味着子串\(s_{i,j}\)可以通过消除消除成一个匹配串，那么我们认为子串\(s_{i,j}\)可以被消除，且令\(f_{i,j,root}=1\)表示可以消除为空串。

发现复杂度为\(O(l^3\sum|p_i|)\)，但是转移②可以使用bitset进行优化，复杂度就会降为\(O(\frac{l^3 \sum |p_i|}{32})\)，而且状态不满，就能很快的跑过了。

计算出可以被消除的区间然后区间DP算出答案。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<vector>
#include<cmath>
//This code is written by Itst
using namespace std;

inline int read(){
	int a = 0;
	char c = getchar();
	bool f = 0;
	while(!isdigit(c) && c != EOF){
		if(c == '-')
			f = 1;
		c = getchar();
	}
	if(c == EOF)
		exit(0);
	while(isdigit(c)){
		a = a * 10 + c - 48;
		c = getchar();
	}
	return f ? -a : a;
}

struct node{
	int ch[26];
}Trie[610];
int dp[251] , cntN = 1 , N , S;
bool can[251][251];
bitset < 610 > f[251][251];
char s[251] , mod[31];
vector < int > End;

void insert(){
	int L = strlen(mod + 1) , cur = 1;
	for(int i = 1 ; i <= L ; ++i){
		if(!Trie[cur].ch[mod[i] - 'a'])
			Trie[cur].ch[mod[i] - 'a'] = ++cntN;
		cur = Trie[cur].ch[mod[i] - 'a'];
	}
	End.push_back(cur);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	scanf("%s" , s + 1);
	N = strlen(s + 1);
	for(int i = 1 ; i <= N ; ++i)
		f[i][i - 1][1] = 1;
	S = read();
	for(int i = 1 ; i <= S ; ++i){
		scanf("%s" , mod + 1);
		insert();
	}
	for(int i = 1 ; i <= N ; ++i)
		for(int j = i ; j ; --j){
			for(int k = 1 ; k <= cntN ; ++k)
				if(f[j][i - 1][k] && Trie[k].ch[s[i] - 'a'])
					f[j][i][Trie[k].ch[s[i] - 'a']] = 1;
			for(int k = j + 1 ; k <= i ; ++k)
				if(can[k][i])
					f[j][i] |= f[j][k - 1];
			for(int k = 0 ; k < S ; ++k)
				if(f[j][i][End[k]])
					f[j][i][1] = 1;
			can[j][i] = f[j][i][1];
		}
	for(int i = 1 ; i <= N ; ++i){
		dp[i] = dp[i - 1] + 1;
		for(int j = i ; j >= 0 ; --j)
			if(can[j][i])
				dp[i] = min(dp[i] , dp[j - 1]);
	}
	cout << dp[N];
	return 0;
}

Codechef STREDUC Reduce string Trie、bitset、区间DP

推荐阅读