poj 1625 AC 자동기+동귀+대수 덧셈

1760 단어 문자열동적 계획-기타
제목: 문자 집합 V와 P 모드 열 (길이 10 이하) 을 주십시오. 이 문자 집합 문자로 구성된 길이가 N이고 임의의 모드 열을 포함하지 않는 문자열은 몇 개입니까?(문자 세트 크기, N<=50, P <=10).
사고방식: 먼저 P개의 모드 열을 AC 로봇으로 만들고 위험 노드(flag 배열)를 표시한다.그리고 회귀구: dp[i][j]는 길이가 i이고 마지막으로 노드 j에 있는 문자열 개수(노드 j는 반드시 안전 노드), 초기 dp[0][1]=1, 기타 dp[i][j]=0.dp[i][j]에서 내보낼 수 있으며 j가 도착할 수 있는 모든 안전 노드son[j], 실행: dp[i+1][son[j]]+=dp[i][j].뿌리에서 i보로 노드 j에 도달하는 데는 n가지 걷는 방법이 있기 때문에 i+1보로 son[j]에 도달하는 걷는 방법은 n을 추가해야 한다.최종 답은 ∑{dp[N][j]|j는 안전 노드}이다.
마지막 수량이 매우 많기 때문에, 수조로 저장해야 한다.
주의: 만약에 바늘로 저장한다면 son[j]은 j에서 한 자모의 가장자리를 통해 직접 도착하는son[j]을 가리킬 뿐만 아니라 몇몇 접두사 바늘을 통과한 후에 한 자모의 가장자리를 통해son[j]에 도달할 수도 있다. (즉son[j]가 반드시 j의 하위 노드는 아니다).수조로 저장하는 것은 마침 이 점을 피했다.
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3fffffff
#define N 505
#define M 55
int n,m,p;
int t[N][M],fail[N],top;
bool flag[N];
char word[M],s[M];
struct dp{
    int num[100];
    bool has;
}dp[M][N];
int res[100];
map hh;
queue q;
void init(){
    int i;
    memset(t, -1, sizeof(t));
    memset(fail, 0, sizeof(fail));
    memset(flag, false, sizeof(flag));
    for(i = 0;i=0&&!res[i];i--);
        if(i==-1)
            putchar('0');
        for(;i>=0;i--)
            printf("%d",res[i]);
        putchar('
');
    }
    return 0;
}
자바 천 백 문05 대상 지향 (002)package 와 import 의 역할 은 무엇 입 니까?
Ubuntu 14.04 업그레이드 또는 Nginx 1.10 설치. *

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage