bzoj 2121 DP

우선 만약에 우리가 i를 처리할 수 있다면 j단을 없앨 수 있습니까? 그러면 바로 dp로 옮길 수 있습니다. w[i]를 전 i로 설정하면 최소한 얼마 남았습니까? 그러면 w[i]=w[j-1](flag[j][i]).
지금 우리는flag[i][j]를 구할 수 있다. 우선 우리는 문자열 그룹을trie로 만든 다음에 직렬 L에서left 위치에서 시작하는 모든 flag를 처리할 수 있다. 그러면 우리는trie에서 계속 아래로 내려갈 수 있다. 표시된 점마다 현재의flag[left][right]를 1로 설정하면 연속적으로 제거할 수 있는 문자열을 처리할 수 있다. 그리고 비슷한 L은 abcde이고 문자열 그룹은ade이다. bc는 먼저 제거할 수 있다.그리고 다시 없애는 상황을 보면 현재의 left에 대해 right에 flag[i][right]=1이 존재한다면 바로 이런 상황입니다. 만약에 우리가 직접 left, i를 처리하면 됩니다. 그러나 우리는 이곳의 flag[i][right]의 i가 left보다 크다는 것을 발견했습니다. 그래서 우리는 어떤 것을 시작으로 하는 모든 flag를 처리할 때 역순으로 처리해야 합니다.
하나의 최적화가 있다. 같은left를 처리할 때 우리는 flag을 처리할 때 두 가지 확장 상황이 있기 때문에 각각의 i에 대해vis[i][j]를 기록하여 현재의left, i노드,right가 j의 상황에 접근했는지 여부를 나타낸다. 이렇게 방문하는 상황이 있으면return이 된다.
반성: 처음에 최적화를 하지 않았는데 금방 a가 됐어요. 나중에 최적화를 추가한 후에 제가 사용한 바늘에trie가 저장되었기 때문에vis수조에서 노드의 번호는 모든 바늘에 번호를 저장해야 해요. 그런데 이 번호는 어떻게 된 일인지 모르겠어요. 신청만 하면 re예요. 뒤에 최적화되지 않은 대로 써요. 단지 node에서 cnt를 신청하기 전에num을 신청하면 re가 돼요. cnt를 신청하면 문제가 없어요.오전 반나절을 바꿔 놓았는데도 어떻게 된 일인지 모르겠다
반성2: 나중에 리턴의 조건이 right>=len이라는 것을 발견했고 right>len이라고 썼기 때문에 정의되지 않은 행위가 생겼다.

/**************************************************************

    Problem: 2121

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:132 ms

    Memory:158900 kb

****************************************************************/

 

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 200

#define maxm 1010

 

using namespace std;

 

struct node{

    int cnt,num; 

    node *child[30];

    node(){ 

        cnt=num=0;

        memset(child,0,sizeof child);

    }

}nodepool[maxm],*totnode,*rot;

 

char s[maxn];

int flag[maxn][maxn],vis[maxn][maxm][maxn],w[maxn];

int n,len;

 

 

void build_trie(){

    int j=1;

    totnode=nodepool; rot=totnode++;

    scanf("%d",&n);

    char ch[maxn];

    while (n--) {

        scanf("%s",ch);

        int len=strlen(ch);

        node *t=rot;

        for (int i=0;i<len;i++) {

            if (!t->child[ch[i]-'a']) t->child[ch[i]-'a']=totnode++,t->child[ch[i]-'a']->num=j++;

            t=t->child[ch[i]-'a'];

        }

        t->cnt=1;

    }

}

 

void make(node *rot,int left,int right) {

    //printf("%d ",rot->num);

    if (rot->cnt) flag[left][right-1]=1;

    if (vis[left][rot->num][right]) return ;

    if (right>=len) return ;

    vis[left][rot->num][right]=1;

    if (rot->child[s[right]-'a']) make(rot->child[s[right]-'a'],left,right+1);

    for (int i=right;i<len;i++) if (flag[right][i]) make(rot,left,i+1);

}

 

int main() {

    scanf("%s",s); len=strlen(s);

    build_trie();

    for (int i=len-1;i>=0;i--) make(rot,i,i);

    /*for (int i=0;i<len;i++) {

        for (int j=0;j<len;j++) printf("%d ",flag[i][j]);

        printf("
");

    }*/

    w[0]=0;

    for (int i=0;i<len;i++) {

        w[i+1]=w[i]+1;

        for (int j=0;j<=i;j++) 

            if (flag[j][i]) w[i+1]=min(w[i+1],w[j]);

        //printf("%d ",w[i]);

    }

    //printf("
");

    printf("%d
",w[len]);

    return 0;

}