hdu2296---ring(AC 로봇 +dp)
Input The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. Each test case starts with a line consisting of two integers: N, M, indicating the string’s length and the number of Jane’s favorite words. Each of the following M lines consists of a favorite word Si. The last line of each test case consists of M integers, while the i-th number indicates the value of Si. Technical Specification
Output For each test case, output the string to engrave on a single line. If there’s more than one possible answer, first output the shortest one. If there are still multiple solutions, output the smallest in lexicographically order.
The answer may be an empty string.
Sample Input
2 7 2 love ever 5 5 5 1 ab 5
Sample Output
lovever abab Hint Sample 1: weight(love) = 5, weight(ever) = 5, so weight(lovever) = 5 + 5 = 10 Sample 2: weight(ab) = 2 * 5 = 10, so weight(abab) = 10
Source The 4th Baidu Cup final
Recommend lcy | We have carefully selected several similar problems for you: 3247 3341 2825 2243 2457
dp[i][j]는 길이가 i이고 노드 j의 최대 권한을 나타낸다. 이 상태에 도달했을 때의 문자열을 기록하기 위해 그룹을 만든다.
/*************************************************************************
> File Name: hdu2296.cpp
> Author: ALex
> Mail: [email protected]
> Created Time: 2015 03 03 17 11 54
************************************************************************/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const double eps = 1e-15;
typedef long long LL;
typedef pair <int, int> PLL;
const int MAX_NODE = 1200;
const int CHILD_NUM = 26;
int dp[100][MAX_NODE];
string path[100][MAX_NODE];
char buf[110][15];
int w[110];
int n, m;
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();
}
void Build_Trie (char buf[], int w)
{
int now = root;
int len = strlen (buf);
for (int i = 0; i < len; ++i)
{
if (next[now][buf[i] - 'a'] == -1)
{
next[now][buf[i] - 'a'] = newnode();
}
now = next[now][buf[i] - 'a'];
}
end[now] = w;
}
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();
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 ()
{
dp[0][0] = 0;
for (int i = 0; i <= n; ++i)
{
for (int j = 0; j <= L; ++j)
{
path[i][j] = "";
}
}
string ans;
ans = "";
int maxs = 0;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < L; ++j)
{
if (dp[i][j] >= 0)
{
for (int k = 0; k < CHILD_NUM; ++k)
{
int l = next[j][k];
string cur = path[i][j];
cur += ('a' + k);
int tmp = dp[i][j];
if (end[l] != 0)
{
tmp += end[l];
}
if (dp[i + 1][l] < tmp)
{
dp[i + 1][l] = tmp;
path[i + 1][l] = cur;
}
else if (dp[i + 1][l] == tmp)
{
if (path[i + 1][l].length() > cur.length())
{
path[i + 1][l] = cur;
}
else if (path[i + 1][l].length() == cur.length() && cur < path[i + 1][l])
{
path[i + 1][l] = cur;
}
}
if (maxs < dp[i + 1][l])
{
maxs = dp[i + 1][l];
ans = path[i + 1][l];
}
else if (maxs == dp[i + 1][l])
{
int len1 = ans.length();
int len2 = path[i + 1][l].length();
if (len1 > len2)
{
ans = path[i + 1][l];
}
else if (len1 == len2 && ans > path[i + 1][l])
{
ans = path[i + 1][l];
}
}
}
}
}
}
cout << ans << endl;
}
}AC;
int main ()
{
int t;
scanf("%d", &t);
while (t--)
{
AC.init();
memset (dp, -1, sizeof(dp));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
{
scanf("%s", buf[i]);
}
for (int i = 1; i <= m; ++i)
{
scanf("%d", &w[i]);
}
for (int i = 1; i <= m; ++i)
{
AC.Build_Trie (buf[i], w[i]);
}
AC.Build_AC();
AC.solve ();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.