JOI2009合宿 DNAの合成

DP
テストケース8〜10あたりだとTLEっぽくなるので想定解ではないはず
O(20*LlogN)
(fprintfになってるのは手動比較のため)

char tmp[160000];
int main(){
	FILE* fp=fopen("out.txt","w");
	int n;scanf("%d",&n);
	scanf("%s",tmp);
	string make=tmp;
	int len=make.size();
	vs pr(n);
	REP(i,n){
		scanf("%s",tmp);
		pr[i]=tmp;
	}
	sort(ALL(pr));
	vi dp(len+1,INF);dp[0]=0;
	REPN(i,len+1,1){
		for(int j=1;j<=19 && i-j>=0;++j){
			if(binary_search(ALL(pr),make.substr(i-j,j+1))){
				dp[i]=min(dp[i],dp[i-j]+1);
			}
		}
		int j=i-1;
		while(j>=0 && i-j<20 && dp[j]>dp[i]){
			dp[j]=dp[i];
			--j;
		}
	}
	fprintf(fp,"%d\n",dp[len]);
	return 0;
}

Trie木という便利なデータ構造を使うと解けるそうです