poj2978--colored stones.cpp

POJ2978

#include<iostream>
using namespace std;
const int M=101;
const int N=6;

int array[M],f[M][1<<5][N];
int num,color,ans;

int min(int a,int b)
{
    return a<b?a:b;
}
    
int main()
{
    int i,j,k,old,variety,temp;
    scanf(" %d %d",&num,&color);
    while(num!=0)
    {
        for(i=1;i<=num;i++)
           scanf(" %d",array+i);           
        memset(f,-1,sizeof(f));
        variety=1<<color;
        for(i=0;i<variety;i++)
           for(j=1;j<=color;j++)
               f[0][i][j]=0;
        for(i=1;i<=num;i++)
           for(j=0;j<variety;j++)
               for(k=1;k<=color;k++)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           
               {
                   if(((1<<(k-1))&j))                   
                   {
                       f[i][j][k]=INT_MAX;
                       f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(array[i]!=k));
                       for(old=1;old<=color;old++)
                       {
                           if(old==k) continue;
                           if((j&(1<<(old-1))))
                             f[i][j][k]=min(f[i][j][k],f[i-1][j-(1<<(k-1))][old]+(array[i]!=k));
                       }    
                   }
               }         
           ans=INT_MAX;
           for(i=0;i<variety;i++)
              for(j=1;j<=color;j++)
                 if(f[num][i][j]>=0&&ans>f[num][i][j])
                    ans=f[num][i][j];
           printf("%d\n",ans);                 
           scanf(" %d %d",&num,&color);
       } 
       system("PAUSE");
       return 0;
}