HDU6212 Zuma(구간 dp)

Zuma

전송문 1 전송문 2 Think about the Zuma Game.You have a row of at most 200 black(0) or white(1) balls on the table at the start. Each three consecutive balls never share the same colour. You also have infinite amount of black and white balls in your hand. On each turn, you can choose a ball in your hand and insert it into the row, including the leftmost place and the rightmost place. Then, if there is a group of three of more balls in the same colour touching, remove these balls. Keep doing this until no more balls can be removed. Find the minimal balls you have to insert to remove all the balls on the table.
Input
The first line of input contains an integer T(1≤T≤100) which is the total number of test cases. Each test case contains a line with a non-empty string of 0 and 1 describing the row of balls at the start.
Output
For each test case, output the case number and the minimal balls required to insert in a line.
Sample Input
4 10101 101001001 1001001001 01001101011001100
Sample Output
Case #1: 4 Case #2: 3 Case #3: 3 Case #4: 2

제목의 뜻

모두 두 가지 색깔의 조마 게임이 있는데 세 개가 연결된 공(또는 세 개 이상)의 공은 제거된다. 이 문자열을 깨끗이 제거한 최소 토구 개수를 물어보자.

분석하다.

정의 dp[i][j]는 구간 i에서 j 사이의 공의 최소 토구 개수를 없애고 cnt[i]로 i개의 연속적인 같은 색깔의 공의 개수를 나타낸다.그렇다면 분명히 조마를 타 본 어린이 신발들은 세 가지가 있는데 하나는 구간을 없애는 방법이 있다. (물론 네가 해 본 적이 없어도 틀림없이 생각할 수 있다) 실제로는 두 가지라고 볼 수 있다.구간을 두 부분으로 나누어 각각 자신의 부분을 제거한다.
dp[ i ][ j ]=min(dp[ i ][ j ],dp[ i ][ k ]+dp[k+1][ j ])
2. 중간 구간을 모두 제거한 후 양쪽 끝의 같은 색상 충돌을 제거합니다.
dp[i][j]=min(dp[i][j], dp[i+1][j-3]+(cnt[i]+cnt[j]가 3보다 작은가)
3. 중간에 공 1개를 넣고 좌우 양쪽 부분을 제거한 후 3부분의 충돌을 제거한다.
dp[ i ][ j ]=min(dp[ i ][ j ],dp[i+1][k−1]+dp[k+1][j−1])
지금 요청
cnt[i]+cnt[j]<=3, 왜냐하면
cnt[i] 및
cnt[j]는 최소한 1이며, 3보다 크면 왼쪽 구간을 먼저 삭제하든 오른쪽 구간을 삭제하든 두 번째 상황을 구성한다.
참고 자료

CODE

#include
#include
#define FOR(i,a,b) for(int i=(a),i##_END_=(b);i<=i##_END_;i++)
#define N 205
char s[N];
int cnt[N],dp[N][N];
inline void Min(int &x,int y) {if(x>y)x=y;}
int main() {
    int t;
    int cas=0;
    scanf("%d",&t);
    while(t--) {
        scanf("%s",s);
        int n=strlen(s),m=1;
        cnt[1]=1;
        FOR(i,1,n-1) {
            if(s[i]==s[i-1])cnt[m]=2;
            else cnt[++m]=1;
        }
        FOR(len,0,m)FOR(i,1,m) {
            int j=i+len;
            if(j<=m&&j>=1) {
                if(len==0)dp[i][j]=3-cnt[i];
                else {
                    dp[i][j]=n<<1;
                    FOR(k,i,j-1)Min(dp[i][j],dp[i][k]+dp[k+1][j]);//            
                    if(!(len&1)) {
                        if(cnt[i]+cnt[j]==2)Min(dp[i][j],dp[i+1][j-1]+1);//    
                        else Min(dp[i][j],dp[i+1][j-1]);
                        if(cnt[i]+cnt[j]<=3)//     
                            for(int k=i+2; k2)
                                if(cnt[k]==1)
                                    Min(dp[i][j],dp[i+1][k-1]+dp[k+1][j-1]);
                    }
                }
            }
        }
        printf("Case #%d: %d
",++cas,dp[1][m]);
    }
    return 0;
}