uva 11552 dp

UVA 11552 - Fewest Flops
k마다 하나의 문자열로 그룹의 문자열 순서를 재구성할 수 있는 문자열재구성 후 문자열을 바꾸면 최소한 몇 개의 문자로 구성할 수 있는지 물어보십시오.연속된 문자를 블록이라고 합니다.
dp[i][j] 테이블 i조는 문자 j로 끝나는 최소 블록 수입니다.그러면 우리는 한 조를 추가하면 블록 수를 줄일 수 있는 상황을 고려할 것이다.1): 이전 그룹의 끝은 이 그룹에서 같은 문자를 찾았으며 현재 블록의 끝은 아닙니다.끝으로 하려면 이 문자가 있는 블록을 뜯어야 하기 때문에 병란한다.2): 현재 그룹은 문자가 하나이며 이전 그룹의 끝과 같습니다.
이 두 가지 상황 모두 블록 수를 1로 줄일 수 있다
dp[i][s] = min(dp[i-1][t] + cnt[i] - flag);flag는 상술한 두 가지 상황을 만족시킬 수 있는지 여부를 나타낸다.

#include 
#include 
#include 
#include 

using namespace std;

const int INF = 999999999;

char s[1005];

int c[1005][26];
int dp[1005][26];
int _cnt[1005];
int k, len;

int main() { // freopen("out.txt", "w", stdout);
    int Tcase;
    scanf ("%d", &Tcase);
    for (; Tcase>0; --Tcase) {
        scanf ("%d%s", &k, s);
        len = strlen(s);

        int _c=-1;
        memset(c, 0, sizeof(c));
        memset(_cnt, 0, sizeof(_cnt));
        while (_cfor (int j=0; jif (c[_c][s[_c*k+j]-'a'] == 0) _cnt[_c]++;
                c[_c][s[_c*k+j]-'a']++;
            }
            _c++;
        }


        for (int i=0; i<=_c; i++) {
            for(int j=0; j<26; j++) {
                dp[i][j] = INF;
            }
        }

        for (int i=0; i<26; i++) {
            if (c[0][i] != 0) dp[0][i] = _cnt[0];
            else dp[0][i] = INF;
        }

        for (int i=1; i<_c i="" class="hljs-keyword">for (int s=0; s<26; s++) {
                for (int t=0; t<26; t++) {
                    if (c[i][s] == 0) continue;
                    if (c[i-1][t] == 0) continue;

                    if (c[i][t] != 0 && (_cnt[i] == 1 || s != t)) {
                        dp[i][s] = min(dp[i][s], dp[i-1][t] + _cnt[i] - 1);// cout << s << " " << t << endl;
                    } else {
                        dp[i][s] = min(dp[i][s], dp[i-1][t] + _cnt[i]);
                    }
                }
            }
        }


        int ans = INF;
        for (int i=0; i<26; i++) {
            ans = min(ans, dp[_c-1][i]);
        }
        printf ("%d
", ans);
    }

    return 0;
}