HDU4758 Walk Through Squares AC 자동기 & &dp
4537 단어 AC 로봇
제목은 이렇다. RD 꼬치 두 개를 정해라. 예를 들어 RRD, DDR 같은 꼬치를 정해라. 그리고 지금은 오른쪽으로 (R) m보, 아래로 (D) n보를 정해진 두 꼬치를 포함할 수 있는 방법이 얼마나 있느냐고 묻는다.
하나의 전통적인 dp 사상은 이런 dp[i][j][x][y][k]이다. i보 R, j보 D, x, y는 두 줄이 각각 얼마나 일치하는지 나타낸다. k는 1,2열이 일치하는 4진수(00,01,10,11, 알잖아. 11은 모두 일치하고 10은 한 줄이 일치한다.그러나 이렇게 하면 공간이 열리지 않는다. 둘째, 어떤 점이 어울리지 않을 때 우리는 현재의 x, y가 어디로 옮길지 모른다. 이때 우리는 자연스럽게 AC자동기를 생각했다. AC자동기가 두 개의 열에 눌리면 열의 총 길이를 초과하지 않는 결점이 필요하다. 그리고 우리가 자동기에서 옮길 때 우리는 어울리지 않을 때 어디로 옮길지 알 수 있다.그래서 다시 정의해 보면 dp[i][j][k][x]k는 자동기의 상태를 나타내고 x는 4진수를 나타낸다.옮길 때 현재 상태 dp[i][j][k][x]에서 dp[i+1][j][nxt1][nxtx]dp[i][j+1]로 옮기는 것을 고려하세요.그 중에서 새로운 상태 nxt와 대응하는 4진수 이동은 AC자동기의 어댑터에 따라 계산해야 한다.만약 짝이 맞지 않을 때 돌아오는 그 결점을 미리 처리한다면 아마도 좀 더 빠를 것이다.내 코드에 dfs를 많이 썼는데 주로 상태가 바뀌었을 때 대응하는 4진수를 미리 처리했기 때문에 옮길 때 한 번만 또는 한 번만 하면 된다.
처음으로 AC 자동기에 있는 dp를 만들고 1A가 됐어요. 너무 좋아요!
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define maxn 2000
#define mod 1000000007
using namespace std;
struct Trie
{
Trie * go[2];
Trie *fail;
int sta;
void init() {
memset(go, 0, sizeof(go)), fail == NULL;
sta = 0;
}
}pool[maxn],*root;
int tot;
void insert(char *c,int type)
{
int len = strlen(c); Trie *p = root;
for (int i = 0; i < len; i++){
int ind = c[i] == 'R' ? 0 : 1;
if (p->go[ind] != NULL){
p = p->go[ind];
}
else{
pool[tot].init();
p->go[ind] = &pool[tot++];
p = p->go[ind];
}
}
p->sta |= type;
}
void getFail()
{
queue<Trie*> que;
que.push(root);
root->fail = NULL;
while (!que.empty())
{
Trie *temp = que.front(); que.pop();
Trie *p = NULL;
for (int i = 0; i < 2; i++){
if (temp->go[i] != NULL){
if (temp == root) temp->go[i]->fail = root;
else{
p = temp->fail;
while (p != NULL){
if (p->go[i] != NULL){
temp->go[i]->fail = p->go[i];
break;
}
p = p->fail;
}
if (p == NULL) temp->go[i]->fail = root;
}
que.push(temp->go[i]);
}
}
}
}
int dfs(Trie *x){
if (x == NULL) return 0;
return x->sta |= dfs(x->fail);
}
int m, n;
int dp[120][120][240][4];
char str[120];
int main()
{
int T; cin >> T;
while (T--)
{
tot = 0; root = &pool[tot++]; root->init();
scanf("%d%d", &m, &n);
for (int i = 1; i <= 2; i++){
scanf("%s", str);
insert(str, i);
}
getFail();
for (int i = 0; i < tot; i++){
dfs(&pool[i]);
}
for (int i = 0; i <= m; i++){
for (int j = 0; j <= n; j++){
for (int k = 0; k <= tot; k++){
for (int x = 0; x < 4; x++){
dp[i][j][k][x] = 0;
}
}
}
}
dp[0][0][0][0] = 1;
for (int i = 0; i <= m; i++){
for (int j = 0; j <= n; j++){
for (int k = 0; k < tot; k++){
for (int x = 0; x < 4; x++){
Trie* p = &pool[k];
if (p->go[0] != NULL){
(dp[i + 1][j][p->go[0] - pool][x | p->go[0]->sta] += dp[i][j][k][x]) %= mod;
}
else{
Trie *temp = p->fail;
while (temp != NULL) {
if (temp->go[0] != NULL){
(dp[i + 1][j][temp->go[0] - pool][x | temp->go[0]->sta] += dp[i][j][k][x]) %= mod;
break;
}
temp = temp->fail;
}
if (temp == NULL) (dp[i + 1][j][0][x | root->sta] += dp[i][j][k][x]) %= mod;
}
if (p->go[1] != NULL){
(dp[i][j + 1][p->go[1] - pool][x | p->go[1]->sta] += dp[i][j][k][x]) %= mod;
}
else{
Trie *temp = p->fail;
while (temp != NULL) {
if (temp->go[1] != NULL){
(dp[i][j + 1][temp->go[1] - pool][x | temp->go[1]->sta] += dp[i][j][k][x]) %= mod;
break;
}
temp = temp->fail;
}
if (temp == NULL) (dp[i][j + 1][0][x | root->sta] += dp[i][j][k][x]) %= mod;
}
}
}
}
}
int ans = 0;
for (int i = 0; i < tot; i++){
ans = ans + dp[m][n][i][3]; ans %= mod;
}
printf("%d
", ans);
}
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
