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); }