Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2010-day2 DNA synthesizer

問題文 : DNAの合成

解法 :
dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると,
M + 1 ~ M + kまでの部分文字列s_kがあるとすると

dp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる.

DNA素を全て確かめるとO(strlen(合成したい文字数) * M)となるが, ある文字列があるかを探すのにTrieを使うことで, O(strlen(合成したい文字数) * (DNA素の長さの最大値))時間でこれが出来るようになる.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int conv[256];

struct Trie {
	bool vis;
	Trie *next[4];
};

Trie stack[1001000], *root;
int idx;

Trie *build()
{
	Trie *ret = &(stack[idx++]);
	for (int i = 0; i < 4; i++) ret->next[i] = (Trie *)0;
	ret->vis = false;
	return (ret);
}

bool find(char *t, Trie *r, bool mode)
{
	for (int i = 0; t[i]; i++){
		char c = conv[t[i]];
		if (!r->next[c] && mode) r->next[c] = build();
		else if (!r->next[c]) return (false);
		r = r->next[c];
	}
	if (mode == true){
		r->vis = true;
	}
	return (r->vis);
}

int main()
{
	static char str[150001];
	static int dp[150001];
	int n, len;
	
	conv['A'] = 0, conv['T'] = 1, conv['G'] = 2, conv['C'] = 3;
	
	root = build();
	scanf("%d", &n);
	scanf("%s", str);
	
	for (int i = 0; i < n; i++){
		char in[32];
		scanf("%s", in);
		find(in, root, true);
	}
	
	for (len = 0; str[len]; len++) dp[len] = 9999999;
	
	for (int i = 0; i < len; i++){
		for (int j = 1; j <= 20 && i + j <= len; j++){
			char c = str[i + j];
			str[i + j] = 0;
			if (find(&str[i], root, false)){
				for (int k = 0; k < j; k++){
					if (!i) dp[i + k] = 1;
					else dp[i + k] = min(dp[i + k], dp[i] + 1);
				}
			}
			str[i + j] = c;
		}
	}
	
	printf("%d\n", dp[len - 1]);
	
	return (0);
}