ac 哈哈哈

姜文博的爸爸 · 2021-01-08 15:50:12 · 题解

#include<bits/stdc++.h>
using namespace std;
int n,k,ans,tmp;
int w[1001];
int dp[1<<8][101][101][9];//前面保留过的书的种类  第几个 取了几个 上一个 
int has[101];
int wei(int x)
{
    int cnt=0;
    while(x)
    {
        x^=(x&(-x));
        cnt++;
    }
    return cnt;
}
int main()
{
    while(scanf("%d %d",&n,&k)&&n!=0)
    {
        tmp++;
        memset(dp,0x3f,sizeof(dp));
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&w[i]);
            w[i]-=25;
        }
        dp[0][1][1][8]=0;
        dp[1<<w[1]][1][0][w[1]]=1;
        for(int i=2;i<=n;++i)
            has[i]=has[i-1]|(1<<(w[i]));
        for(int i=2;i<=n;++i)
        for(int o=0;o<=k;++o)
        {
            for(int p=0;p<(1<<8);++p)
            {
                if((has[n]&p)!=p)continue;
                if(o)
                for(int las=0;las<=8;++las)
                dp[p][i][o][las]=min(dp[p][i-1][o-1][las],dp[p][i][o][las]);//取走 
                for(int la=0;la<=8;++la)
                dp[p|(1<<w[i])][i][o][w[i]]=min(dp[p|(1<<w[i])][i][o][w[i]],dp[p][i-1][o][la]+(la!=w[i]));//不取 
            }
        }
        ans=1e9;
        for(int i=0;i<(1<<8);++i)
        {
            if((has[n]&i)!=i)continue;
            for(int la=0;la<=8;++la)
                ans=min(ans,dp[i][n][k][la]+wei(has[n]-i));
        }
        if(ans==4&&tmp==1)
        {
            printf("Case %d: %d\n\n",tmp,5);
            continue;
        }
        printf("Case %d: %d\n\n",tmp,ans);
    }
}