Zuma 문제 풀이

신기한 전송문 제목:

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

문제풀이: 돌아가는 과정을 고려하여 모두 없애는 최소한의 용도로 설정하면 우리는 의심할 여지없이 이 몇 가지 소법이 있다.중간에 공 1개가 있고 그 좌우 양측의 부분을 제거한 후 3부분의 충돌을 제거한다. Dp[i][j]=min(Dp[i][j], Dp[i][k]+Dp[k+1][j]).2. 머리와 꼬리의 색깔이 같으면 I) 머리와 꼬리를 합치면 세 개보다 크면 바로 사라지고 Dp[i][j]=min(Dp[i][j], Dp[i+1][j-1]로 옮길 수 있다.II) 3개가 부족하면 몇 개를 추가하여 Dp[i][j]=min(Dp[i][j], Dp[i+1][j-1]+3 - a[i]- a[j])로 옮길 수 있다.III) 머리와 꼬리가 충분하든 간에 중간에서 하나를 찾은 다음에 삼소를 찾을 수 있다. 우리가 정의한 것은 귀속적인 느낌이 있기 때문에 사실 삼소와 이소는 다소를 포함한다.이전: Dp[i][j]=min(Dp[i][j], Dp[i+1][k-3]+Dp[k+1][j-3])) 그러나 중간에 있을 수 없는 것은 각각 양쪽 개수와 3개보다 크므로 삼소할 수 없기 때문에 a[i]+a[j]<4를 내놓으면 된다.Dp[i][i]=3 - ball[i]에 초기화합니다.sum . 코드:

#include
#include
#include
#define f(x,y,z) for (int (x);x<=y;x++)
using namespace std;
const int size = 1000; 
const int inf = 100000;
struct Ball{
    int sum,color;
}ball[size];int cnt;
int T , n ,kase=0;
int dp[size][size];
char s[size];
int main()
{
    scanf("%d",&T);
    while (    T--)
    {
        memset(s,NULL,sizeof s);
        memset(dp,0,sizeof dp);
        scanf("%s",s);    
        cnt=1;ball[1].color = (int)( s[0] -'0');ball[1].sum=1;
        for(int i=1;i<strlen(s);i++)
        if (ball[cnt].color != (int) (s[i]-'0') )  ball[++cnt]=(Ball){1,(int) (s[i]-'0')};
        else ball[cnt].sum++;

            for (int len = 0;len<=cnt;len++)
            {
                for (int i=1;i<=cnt;i++)
                {
                    int j = i + len;
                    if (j<=cnt&&1<=j)
                    {
                        dp[i][j] = inf;
                        if (i==j)
                        {
                            dp[i][j] = 3 - ball[i].sum;
                        }
                        else 
                        {
                            for (int k = i ; k <= j ; k++)
                            dp[i][j] = min(dp[i][j] , dp[i][k]+dp[k+1][j] );
                            if (ball[i].color == ball[j].color)
                            {
                                if (ball[i].sum+ball[j].sum>=3) dp[i][j] = min(dp[i][j] , dp[i+1][j-1]);
                                else dp[i][j] = min(dp[i][j] , dp[i+1][j-1] + 3- ball[i].sum-ball[j].sum); 
                                if (ball[i].sum+ball[j].sum < 4)
                                {
                                    for (int ii=i+1 ; iiif (ball[i].color==ball[ii].color && ball[ii].sum==1) 
                                    dp[i][j]=min(dp[i][j] , dp[i+1][ii-1] + dp[ii+1][j-1]);
                                }                
                            }    
                        }
                    }        
                }    
            }
     printf("Case #%d: ",++kase);
    printf("%d",dp[1][cnt]);
    putchar('
');
    }
    return 0;
}