BZOJ 1032 JSOI 2007 초기 Zuma 동적 기획

제목 대의: 조마 서열을 정하고 색깔을 선택해서 쏘기♂구슬이 나오면 물어보면 가장 적게 쏜다.♂구슬이 얼마나 나오느냐
입력법이 요즘 점점 이상해지고 있어요. 0.0.
우선 우리는 연속적으로 같은 구슬을 모두 움츠려 f[i][j]로 하여금 i부터 시작하는 j개의 구슬의 최소 제거 횟수를 나타낸다
초기값 f[i][1]=cnt[i]=1?2:1
그리고 각 구간에 대해 우리는 중간점을 하나하나 열거하여 둘로 나누어 화해를 구한다
만약 이 구간의 양쪽 점 색깔이 같다면, 우리는 중간을 없애고, 그 다음에 양쪽을 다시 1개 또는 0개를 보충할 수 있다
니마 구슬 색깔은 0... 이것 때문에 한참 동안 WA 참~! @#$%^&*()
그리고 이 문제는 BUG가 있어요. 제 코드는 흩어진 구슬 세 개가 모여있는 건 생각할 수 없지만 AC가 됐어요.
예:
7
1 2 2 1 3 3 1
ans:2
그래서 저는 두 번째 버전을 썼습니다. 구간 양측의 구슬이 모두 단일할 때 구간 내부에서 세 번째 단일한 구슬을 찾았는데 데이터 원인 WA가 떨어졌습니다. 하지만 이 데이터를 통과할 수 있습니다.
공식적으로 데이터를 업데이트해주셨으면 좋겠습니다~ (@^ ^@)~

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 510
using namespace std;
int n;
pair<int,int>a[M];
int f[M][M];
int main()
{
	int i,j,k,x;
	cin>>n;
	a[0].first=19980402;
	for(i=1,j=0;i<=n;i++)
	{
		scanf("%d",&x);
		if(x!=a[j].first)
			a[++j].first=x;
		a[j].second++;
	}
	n=j;
	memset(f,0x3f,sizeof f);
	for(i=1;i<=n;i++)
		f[i][1]=a[i].second==1?2:1;
	for(j=2;j<=n;j++)
		for(i=1;i+j-1<=n;i++)
		{
			if(a[i].first==a[i+j-1].first)
				f[i][j]=f[i+1][j-2]+(a[i].second+a[i+j-1].second==2?1:0);
			for(k=1;k<j;k++)
				f[i][j]=min(f[i][j],f[i][k]+f[i+k][j-k]);
		}
	cout<<f[1][n]<<endl;
}

그 데이터를 넘을 수 있는데 WA에서 떨어진 코드예요.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 510
using namespace std;
int n;
pair<int,int>a[M];
int f[M][M];
int main()
{
    int i,j,k,x;
    cin>>n;
    a[0].first=19980402;
    for(i=1,j=0;i<=n;i++)
    {
        scanf("%d",&x);
        if(x!=a[j].first)
            a[++j].first=x;
        a[j].second++;
    }
    n=j;
    memset(f,0x3f,sizeof f);
    for(i=1;i<=n;i++)
        f[i][1]=a[i].second==1?2:1;
    for(j=2;j<=n;j++)
        for(i=1;i+j-1<=n;i++)
        {
            if(a[i].first==a[i+j-1].first)
            {
            	if(a[i].second+a[i+j-1].second==2)
           		{
					 f[i][j]=f[i+1][j-2]+1;
					 for(k=2;k<j;k++)
					 	if(a[i+k-1].first==a[i].first&&a[i+k-1].second==1)
					 		f[i][j]=min(f[i][j],f[i+1][k-2]+f[i+k][j-k-1]);
					 		
			    }
           		else
                f[i][j]=f[i+1][j-2];
            }
            for(k=1;k<j;k++)
                f[i][j]=min(f[i][j],f[i][k]+f[i+k][j-k]);
        }
    cout<<f[1][n]<<endl;
}