LOJ: 1422 - Halloween Costumes

LOJ: 1422 - Halloween Costumes

///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     102
#define inf    2000000000
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int n,ar[MX+2],br[MX+2],dp[MX][MX];
int go(int l,int r) {
    if(l==r) return 1;///Throw this
    int &ret=dp[l][r];
    if(ret!=-1) return ret;
    ret=1+go(l+1,r);///Buy,Wear&Throw here;
    for(int i=l+1; i<=r; i++) {
        if( br[l]==br[i] ) {
            ret=min(ret, go(l+1,i-1)+go(i,r) );
        }
    }
    return ret;
}
int main() {
    int tc,cs=1,i,j,k;
    S(tc);
    while(tc--) {
        S(n);
        fr(i,1,n)S(ar[i]);
        k=0;
        br[++k]=ar[1];
        fr(i,2,n) {
            if(ar[i]!=ar[i-1])br[++k]=ar[i];
        }
        n=k;
        fr(i,1,n)fr(j,1,n)dp[i][j]=-1;
        int ans=go(1,n);
        printf("Case %d: %d\n",cs++,ans);
    }
    return 0;
}