Pku2978 Colored stones

题目链接：Click here

Solution：

状压dp，考虑\(f[i][j][k]\)表示当前到了第i个石头，颜色状态为j，选取的最后一个石头颜色为k时能够留下的石头的最大数量

转移也很好转移，枚举所有状态，再枚举上次转移过来的状态的最后一个颜色，然后暴力转移就行了

最后查找一下所有情况下的最大值，输出n-max就行了

Code：

#include<cstdio>

#include<ctype.h>

#include<cstring>

#include<algorithm>

using namespace std;

int n,m,f[101][(1<<8)-1][7];

int b[7]={0,1};

int read(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}

    return x*f;

}

int main(){

    for(int i=2;i<=6;i++) b[i]=b[i-1]*2;

    begin:n=read(),m=read();

    if(n==0&&m==0) return 0;

    memset(f,0,sizeof(f));

    int num=b[m+1]-1,ans=0;

    for(int i=1;i<=n;i++){

        int x=read();

        for(int s=0;s<=num;s++){

            if(!(s&b[x]))

                for(int j=1;j<=m;j++){

                    if(!(s&b[j])) continue;

                    f[i][s|b[x]][x]=max(f[i][s|b[x]][x],f[i-1][s][j]+1);

                    f[i][s][j]=max(f[i][s][j],f[i-1][s][j]);

                }

            else

                for(int j=1;j<=m;j++){

                    if(j==x) f[i][s][x]=max(f[i][s][x],f[i-1][s][j]+1);

                    else if(s&b[j]) f[i][s][j]=max(f[i][s][j],f[i-1][s][j]);

                }

        }

    }

    for(int i=1;i<=m;i++)

        for(int s=0;s<=num;s++)

            if(s&b[i]) ans=max(ans,f[n][s][i]);

    printf("%d\n",n-ans);goto begin;

}

巴特西

Pku2978 Colored stones

Solution：

Code：

最新文章

热门文章