JOI2010春合宿Day2 DNA の合成(DNA synthesizer)
問題を解くやる気を出すために(それと説明したり論理的に考えるのが苦手なので)、よさそうな問題を解いたときブログを書くことにします。
説明に関しては間違いだらけなはずなので指摘などしてくださると嬉しいです。
解法
なんとなくTrie木が必要そうと思ったので、Trie木を勉強しました。
実装も楽でよいですね。
もらうDPを書きました。
とします。
あるDNAの後ろにある素DNAを合成するとき、重なっている部分の長さは(その素DNAの長さよりも短ければ)いくつでもよいですよね。
それを考えると、目的の文字列をTとすると漸化式は
です。
このとき計算量はです。
文字列の一致判定にTrie木を使うとなので間に合います。
コード
最近REP(0,n)みたいな闇マクロに興味があったりします。
using namespace std; #define int long long struct Trie { bool isEnd; Trie *next[4]; Trie() { isEnd = false; fill_n(next, 4, (Trie*)NULL); } }; int N; string T, S[50000]; Trie *root; int dp[150000]; void Convert(string &s) { for (int i = 0; i < s.size(); i++) { if (s[i] == 'T') s[i] = 'B'; if (s[i] == 'G') s[i] = 'D'; } } bool Find(char *c, Trie *t) { if (*c == '\0') return t->isEnd; if (t->next[*c - 'A'] == NULL) return false; return Find(c + 1, t->next[*c - 'A']); } void Insert(char *c, Trie *t) { if (*c == '\0') { t->isEnd = true; return; } if (t->next[*c - 'A'] == NULL) t->next[*c - 'A'] = new Trie(); Insert(c + 1, t->next[*c - 'A']); } signed main() { root = new Trie(); cin >> N >> T; Convert(T); for (int i = 0; i < N; i++) { cin >> S[i]; Convert(S[i]); Insert((char*)S[i].c_str(), root); } fill_n(dp, T.size(), LLONG_MAX / 2); string start; for (int i = 0; i < T.size(); i++) { start.push_back(T[i]); if (Find((char*)start.c_str(), root)) dp[i] = 1; } for (int i = 1; i < T.size(); i++) { string s; s.push_back(T[i]); int mi = LLONG_MAX / 2; for (int j = 1; j < 20 && i - j >= 0; j++) { s = T[i - j] + s; mi = min(mi, dp[i - j]); if (Find((char*)s.c_str(), root)) dp[i] = min(dp[i], mi + 1); } } printf("%lld\n", dp[T.size() - 1]); return 0; }