ZOJ3545---Rescue the Rabbit(AC 로봇 + dp)
A rabbit’s genes can be expressed as a string whose length is l (1 ≤ l ≤ 100) containing only ‘A’, ‘G’, ‘T’, ‘C’. There is no doubt that Dr. X had a in-depth research on the rabbits’ genes. He found that if a rabbit gene contained a particular gene segment, we could consider it as a good rabbit, or sometimes a bad rabbit. And we use a value W to measure this index.
We can make a example, if a rabbit has gene segment “ATG”, its W would plus 4; and if has gene segment “TGC”, its W plus -3. So if a rabbit’s gene string is “ATGC”, its W is 1 due to ATGC contains both “ATG”(+4) and “TGC”(-3). And if another rabbit’s gene string is “ATGATG”, its W is 4 due to one gene segment can be calculate only once.
Because there are enough rabbits on Earth before 2012, so we can assume we can get any genes with different structure. Now Dr. X want to find a rabbit whose gene has highest W value. There are so many different genes with length l, and Dr. X is not good at programming, can you help him to figure out the W value of the best rabbit. Input
There are multiple test cases. For each case the first line is two integers n (1 ≤ n ≤ 10),l (1 ≤ l ≤ 100), indicating the number of the particular gene segment and the length of rabbits’ genes.
The next n lines each line contains a string DNAi and an integer wi (|wi| ≤ 100), indicating this gene segment and the value it can contribute to a rabbit’s W. Output
For each test case, output an integer indicating the W value of the best rabbit. If we found this value is negative, you should output “No Rabbit after 2012!”. Sample Input
2 4 ATG 4 TGC -3
1 6 TGC 4
4 1 A -1 T -2 G -3 C -4
Sample Output
4 4 No Rabbit after 2012!
Hint
case 1:we can find a rabbit whose gene string is ATGG(4), or ATGA(4) etc. case 2:we can find a rabbit whose gene string is TGCTGC(4), or TGCCCC(4) etc. case 3:any gene string whose length is 1 has a negative W. Author: HONG, Qize Contest: The 2011 ACM-ICPC Asia Dalian Regional Contest
역시 간단한 문제입니다. dp, dp[i][j][k]는 길이가 i이고 노드 j, 상태가 k의 타당성을 나타낸다. 그리고 자동기 이동을 구축하면 됩니다. 수조가 열리지 않기 때문에 스크롤 수조를 사용해야 합니다. 그러나 스크롤 수조를 사용할 때 지난번에 사용한 것은 이번에 사용한 것을 방해해서는 안 된다는 것을 기억하세요.
/************************************************************************* > File Name: ZOJ3545.cpp > Author: ALex > Mail: [email protected] > Created Time: 2015 04 20 15 42 47 ************************************************************************/
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
#include <set>
#include <vector>
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int MAX_NODE = 1010;
const int CHILD_NUM = 4;
bool dp[2][MAX_NODE][1100];
int mp[15];
struct AC_Automation
{
int next[MAX_NODE][CHILD_NUM];
int fail[MAX_NODE];
int end[MAX_NODE];
int root, L;
int newnode()
{
for (int i = 0; i < CHILD_NUM; ++i)
{
next[L][i] = -1;
}
end[L++] = 0;
return L - 1;
}
void init ()
{
L = 0;
root = newnode();
}
int ID(char c)
{
if (c == 'A')
{
return 0;
}
if (c == 'G')
{
return 1;
}
if (c == 'T')
{
return 2;
}
return 3;
}
void Build_Trie (char buf[], int id)
{
int now = root;
int len = strlen (buf);
for (int i = 0; i < len; ++i)
{
if (next[now][ID(buf[i])] == -1)
{
next[now][ID(buf[i])] = newnode();
}
now = next[now][ID(buf[i])];
}
end[now] |= (1 << id);
}
void Build_AC ()
{
queue <int> qu;
fail[root] = root;
for (int i = 0; i < CHILD_NUM; ++i)
{
if (next[root][i] == -1)
{
next[root][i] = root;
}
else
{
fail[next[root][i]] = root;
qu.push (next[root][i]);
}
}
while (!qu.empty())
{
int now = qu.front();
qu.pop();
end[now] |= end[fail[now]];
for (int i = 0; i < CHILD_NUM; ++i)
{
if (next[now][i] == -1)
{
next[now][i] = next[fail[now]][i];
}
else
{
fail[next[now][i]] = next[fail[now]][i];
qu.push(next[now][i]);
}
}
}
}
void solve(int l, int n)
{
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
int now = 1;
for (int i = 0; i < l; ++i)
{
memset(dp[now], 0, sizeof(dp[now]));
for (int j = 0; j < L; ++j)
{
for (int k = 0; k < (1 << n); ++k)
{
for (int q = 0; q < 4; ++q)
{
int nxt = next[j][q];
dp[now][nxt][k | end[nxt]] = (dp[now][nxt][k | end[nxt]] || dp[now ^ 1][j][k]);
}
}
}
now ^= 1;
}
int ans = -inf;
for (int i = 0; i < L; ++i)
{
for (int j = 0; j < (1 << n); ++j)
{
if (dp[now ^ 1][i][j])
{
int w = 0;
for (int k = 0; k < n; ++k)
{
if (j & (1 << k))
{
w += mp[k];
}
}
ans = max(ans, w);
}
}
}
if (ans < 0)
{
printf("No Rabbit after 2012!
");
}
else
{
printf("%d
", ans);
}
}
}AC;
char str[110];
int main()
{
int n, l, w;
while (~scanf("%d%d", &n, &l))
{
AC.init();
for (int i = 0; i < n; ++i)
{
scanf("%s%d", str, &w);
AC.Build_Trie(str, i);
mp[i] = w;
}
AC.Build_AC();
AC.solve(l, n);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU4758 Walk Through Squares AC 자동기 & &dp이 문제는 그때 할 때 수론제라고 생각했는데 01열 두 개가 포함돼 있었다. 경기 후에 문자열이라고 듣고 그럴 가능성이 높았다.어제 팀원들이 이 문제를 물었는데 AC자동기를 배운 후에 많이 간단해졌다고 느꼈다.그때는...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.