2013 다 교 제3 회 hdu 4628 Pieces

hdu 4628
제목:http://acm.hdu.edu.cn/showproblem.php?pid=4628
사고: 상 압 한 다음 에 check 함 수 를 써 서 답장 여 부 를 판단 하면 됩 니 다.
이 문 제 는 정말 어이 가 없다.오후 부터 우 리 는 욕심 을 내 고 싶 었 다. 그리고 나 서 나 는 바로 'WA' 를 두 드 렸 다. 나중에 데 이 터 를 찾 아 욕심 의 생각 을 뒤 집 었 다. 그리고 바로 상태 압축 DP 를 시작 했다. 첫 번 째 는 기억 화, TLE 를 썼 다. 바로 가지치기 최적화, 제출 하 는 지, 아니면 TLE 인지, 그리고 욕심 의 그 답 을 가지치기 로 가 져 왔 다. 이렇게 조금 줄 이 고 한 번 내 고 계속 TLE.어 쩔 수 없 이 고 쳐 버 리 고 순환 적 으로 전달 하 는 것 을 썼 습 니 다. 몇 번 이나 사 귀 었 습 니 다. 계속 TLE, 한 동료 와 최적화 되 었 습 니 다. 여러 가지 방법 은 어쨌든 TLE 입 니 다.나중에 동료 가 안 되 겠 다 고 하 자 바로 올 라 와 서 제 코드 에 상 태 를 옮 겨 서 가방 을 만 들 었 는데 이렇게 넘 어 갔 어 요.
밥 을 먹고 나 서 나 는 바로 인터넷 에 가서 다른 사람 이 어떻게 썼 는 지 보 았 는데, 보 니 갑자기 내 가 TLE 를 배 우 는 것 이 정말 당연 하고, 기 예 를 잘 배우 지 못 한 다 는 것 을 느 꼈 다.
이것 은 내 가 원래 쓴 코드 이다.

for(int i = S-1;i>=0;i--)
{
	d[i] = INF;
    for(int j = i+1;j<=S;j++)
    {
		if((i|j)==j)
		{
			if(is[j-i])
			{
				d[i] = min(d[i],d[j]+1);
			}
		}
	}
}

이것 은 내 가 인터넷 의 코드 를 본 후에 고 친 코드 이다.

for(int i = S-1;i>=0;i--)
{
	d[i] = INF;
	for(int j = i+1;j<=S;j = (j+1)|i)
	{
		if(is[j-i])
		{
			d[i] = min(d[i],d[j]+1);
		}
	}
}

관건 은 안에 있 는 j 의 순환, 즉 매 거 가능 한 상태 일 때, j = (j + 1) | i 입 니 다. 이렇게 하면 많은 상 태 를 줄 이 고 많은 시간 을 단축 시 킬 수 있 습 니 다.
다음은 전체 코드 입 니 다.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include<algorithm>
using namespace std;

const int INF = 1000000000 ;

char str[22];

int n;

char tmp[22];

int check(int s)
{
    //printf("s = %d
",s);
    int c=0;
    for(int i=0;i<n;i++)
    {
        if((s&(1<<i))!=0)
        {
            tmp[c++] = str[i];
        }
    }
    tmp[c] = '\0';
    //puts(tmp);
    for(int i=0,j=c-1;i<j;)
    {
        if(tmp[i]!=tmp[j])
        {
            return 0;
        }
        else
        {
            i++;
            j--;
        }
    }
    return 1;
}

int d[1<<17];

int is[1<<17];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%s",str);
        n = strlen(str);
       int S = (1<<(n))-1;
       for(int i = 0;i<=S;i++)
       {
           is[i]=0;
           if(check(i)) is[i]=1;
       }
       d[S] = 0;
       for(int i = S-1;i>=0;i--)
       {
           d[i] = INF;
           for(int j = i+1;j<=S;j = (j+1)|i)
           {
                if(is[j-i])
                {
                    d[i] = min(d[i],d[j]+1);
                }
           }
       }
       printf("%d
",d[0]);
    }
    return 0;
}