M_sea

UVa12235 Help Bubu
UVaLuogu分析因为书本的高度最多只有 $8$ 种,所以可以考虑状压 DP 。设 $dp_{i,j,S,l}$...
扫描右侧二维码阅读全文
09
2019/08

UVa12235 Help Bubu

UVa

Luogu

分析

因为书本的高度最多只有 $8$ 种,所以可以考虑状压 DP 。

设 $dp_{i,j,S,l}$ 表示前 $i$ 本书,拿掉了 $j$ 本,拿掉的高度集合是 $S$ ,最后拿的高度是 $l$ 的最小混乱度。

转移讨论一下当前的拿掉还是不拿掉就好了。

然后如果一种高度全部被拿掉了,那么它会贡献 $1$ 的混乱度,记得要加上去。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

int n,k;
int a[N],in[10];
int dp[2][N][256][10];

int main() {
    int T=0;
    while (n=read(),k=read()) {
        memset(in,0,sizeof(in));
        for (re int i=1;i<=n;++i) a[i]=read()-24,in[a[i]]=1;
        memset(dp[0],0x3f,sizeof(dp[0])),dp[0][0][255][0]=0;
        for (re int i=0;i<n;++i) {
            int now=i&1,nxt=now^1; memset(dp[nxt],0x3f,sizeof(dp[nxt]));
            for (re int j=0;j<=k;++j)
                for (re int S=0;S<256;++S)
                    for (re int l=0;l<=8;++l) {
                        if (dp[now][j][S][l]==0x3f3f3f3f) continue;
                        if (j<k) chkmin(dp[nxt][j+1][S][l],dp[now][j][S][l]);
                        int tmp=(S&(1<<(a[i+1]-1)))?(S^(1<<(a[i+1]-1))):S;
                        chkmin(dp[nxt][j][tmp][a[i+1]],dp[now][j][S][l]+(a[i+1]!=l));
                    }
        }
        int ans=0x3f3f3f3f;
        for (re int S=0;S<256;++S)
            for (re int i=0;i<=8;++i) {
                if (dp[n&1][k][S][i]==0x3f3f3f3f) continue;
                int tmp=dp[n&1][k][S][i];
                for (re int j=1;j<=8;++j)
                    if (in[j]&&(S&(1<<(j-1)))) ++tmp;
                chkmin(ans,tmp);
            }
        printf("Case %d: %d\n\n",++T,ans);
    }
    return 0;
}
最后修改:2019 年 08 月 09 日 05 : 33 PM

发表评论