poj-3267

    // 740K 266MS   G++
    #include <cstdio>  
    #include <string>  
    #include <cstring>  
    #include <iostream>  
      
    using namespace std;  
      
    int DP[305][305]; //  
      
    int DP2[305];  
      
    string dict[605];  
    int W; // num of dict  
    int L; // length of message  
      
    string message;  
      
    #define INF 999999  
      
    int getRemoveNum(int begin, int end, const string & cmpStr, int * lastMatch) { // -1 means no solution  
        // cout<<"getRemoveNum "<<begin<<" "<<end<<" "<<cmpStr<<endl;  
        if (cmpStr.size() > end - begin +1) { // if str length even longer than message part  
            return -1;  
        }  
        int matchNum = 0;  
        int beginPos = begin;  
        int cmpStrSize = cmpStr.size();  
        for (int i = 0; i <= cmpStrSize - 1; i++) {  
      
            while(beginPos <= end) {  
                if (message[beginPos++] == cmpStr[i]) {  
                    if (i == cmpStrSize - 1) {  
                        *lastMatch = beginPos-1;  
                    }  
                    // firstMatch  
                    matchNum++;  
                    break;  
                }  
            }  
            if (beginPos > end) {  
                break;  
            }  
        }  
        if (matchNum == cmpStrSize) { // if all char in   
            // cout<<begin<<" "<<end<<" "<<cmpStr<<" "<<end - begin + 1 - cmpStrSize<<" "<<*lastMatch<<endl;  
            return (end - begin + 1 - cmpStrSize);  
        } else {  
            return -1;  
        }  
    }  
      
    void solve2() {  
        memset(DP2, 0xFF, sizeof(DP2));  
      
        for (int i = L-1; i >= 0; i--) {  
            int minDP = INF;  
            int lastMatch;  
            if (i == L-1) {  
                for (int k = 0; k < W; k++) { // process the whole str(i<->j)  
                    int res = getRemoveNum(i, L-1, dict[k], &lastMatch);  
                    if (res != -1) {  
                        minDP = minDP < res ? minDP: res;  
                    }  
                }  
                if (minDP == INF) {  
                    DP2[L-1] = -1;  
                } else {  
                    DP2[L-1] = minDP;  
                }  
                // printf("%d %d
", i, DP2[i]);  
            } else {  
                for (int k = 0; k < W; k++) { // process the whole str(i<->j)  
                    int res = getRemoveNum(i, L-1, dict[k], &lastMatch);  
                    if (res != -1) { // if can match some  
                        if (DP2[lastMatch + 1] != -1) {  
                            // int res1 = res - (firstMatch -1 + 1 - DP2[firstMatch + dict[k].size()]);  
                            int res1 = res - (L - 1 - lastMatch - DP2[lastMatch+1]); 
                            minDP = minDP < res1 ? minDP : res1;  
                        } else {
                            minDP = minDP < res ? minDP : res;
                        }  
                    }  
                }  
                if (minDP == INF) {  
                    if (DP2[i+1] == -1) {  
                        DP2[i] = -1;
                    } else {  
                        DP2[i] = DP2[i+1] + 1;  
                    }  
                } else {  
                    DP2[i] = minDP;  
                }  
                // printf("%d %d
", i, DP2[i]);  
            }  
        }  
        printf("%d
", DP2[0]);  
    }  
      
      
    // void solve() {  
    //     memset(DP, 0xFF, sizeof(DP)); // all init to -1 means no match  
      
    //     for (int i = L-1; i >= 0; i--) {  
    //         for (int j = 0; j <= L-1; j++) {  
      
    //             if (i > j) {  
    //                 continue;  
    //             }  
    //             // printf("%d %d
", i, j);  
    //             int minDP = INF;  
      
    //             for (int k = 0; k < W; k++) { // process the whole str(i<->j)  
    //                 int res = getRemoveNum(i, j, dict[k]);  
    //                 if (res != -1) {  
    //                     minDP = minDP < res ? minDP: res;  
    //                 }  
    //             }  
      
    //             for (int k = i; k <= j-1; k++) { // get the sum of i<->k k+1<->j  
    //                 if (DP[i][k] != -1 && DP[k+1][j] != -1) {  
    //                     int sum = DP[i][k] + DP[k+1][j];  
    //                     minDP = sum < minDP ? sum: minDP;  
    //                 }  
    //             }  
    //             DP[i][j] = (minDP == INF ? -1: minDP);  
    //         }  
    //     }  
    //     printf("%d
", DP[0][L-1]);  
    // }  
      
    int main() {  
        while(scanf("%d %d", &W, &L) !=EOF) {  
            cin>>message;  
            for (int i = 0; i < W; i++) {  
                cin>>dict[i];  
            }  
            solve2();  
        }  
    }  

순수 DP 각도에서 보면 간단한 DP 문제(1차원 DP 행렬만 사용)이지만 상태 이동 방정식은 생각하기 어려울 것 같다.
처음에 소박한 DP와 2차원 매트릭스 DP[i][j]는 메시지 i에서 j까지의 구간에서 지울 수 있는 최소 자모를 표시했습니다.
DP[i][j]에는 다음과 같은 수치가 있습니다. i에서 j까지 하나의 큰 문자열(분할하지 않음)이 일치하고 i에서 k와 k에서 j(분할) 두 문자열(i<=k<=j)이 일치하는 것과 (D[i][k]+D[k][j])의 최소값이 일치합니다.
그때 썼을 때 TLE를 달라고 생각했는데 역시, 그래도 답이 맞았으니 이렇게 자신을 위로할 수밖에 없었다.
나중에 검색해 보니 생각의 방향이 의외로 간단했다. 1차원 DP만 있으면 충분하다. DP[i]는 메시지 메시지가 1에서 L(message 말미)까지 일치하는 최소 삭제 수(왜 0에서 i가 아닌 것은 후부터 처리할 때 더욱 편리하기 때문이다)를 표시했다. 그러면 DP[i]의 수치는 이런 상황이 있을 것이다.
만약 DP[i]에서 어떤 dict의 단어와 일치하지 않는다면 DP[i]=DP[i+1]+1;
dict어 (i부터 최대 L까지) 에 일치할 수 있다면 최소 삭제 수가 N이면 두 가지 상황이 있습니다.
일치하는 dict어의 마지막 알파벳을 설정하면 메시지 위치가 k(마지막 일치하는 위치)입니다. 그러면 k+1에서 L 사이에 문자가 하나 더 있습니다. 이 문자의 최소 삭제 전에도 구했습니다. DP[K+1],
만약 DP[k+1] = -1 (그리고 k+1에서 L까지 완전한 일치가 없다면) DP[i] = N (i에서 k까지의 일치만 유효합니다)
만약DP[k+1]=M이라면 k+1에서 L까지의 문자가 다른 일치가 있다는 것을 의미한다. N은 반드시 가장 적은 삭제수가 아니다(N은 전체 k+1에서 L까지의 문자를 모두 삭제해야 한다고 생각하지만 사실 k+1에서 L까지의 문자는 삭제하지 않아도 되기 때문에 반드시 N보다 최소한 1의 삭제수가 있어야 한다).
k+1에서 L까지의 문자열에서 DP[k+1]는 이 단락이 일치하는 최소 삭제수를 나타낸다. 그러면 삭제되지 말아야 할 문자수 V는 (L-K-1+1-DP[k+1])이고 N은 사실 V를 많이 계산한다.
따라서 이 부분의 최소 삭제 수는 N - V = N - L + K + DP [K+1],
주의해야 할 것은 매칭은 dict의 모든 문자열을 매칭하는 것이다. 위의 이 과정은 특정한 dict[p]에 대한 것이기 때문에 매칭 중의 최소 값을 얻어야 이 부분의 진정한 최소 삭제 수가 된다.
0에서 i가 아닌 i에서 L로 치우치는 이유는 다음과 같다.
i에서 L까지 새로운 매칭을 하는 것은 바로 i부터 매칭하는 것이다. (0부터 매칭할 수 없다. 그러면 의미를 잃고 새로 추가된 문자의 가치를 나타낼 수 없다)
그러나 0에서 i에 불과하다면 새로운 매칭은 i에서 반대로 매칭해야 한다. 그러면 불편하다. 본질은 똑같다. 매번 새로운 문자가 확장될 때마다 이 문자부터 매칭한다.