记录编号	321063	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺三]宁采臣的书架	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	1.525 s
提交时间	2016-10-13 10:25:08	内存使用	2.68 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=0x7f7f7f7f;
int b[111], d[2][111][1<<8][11], o[1<<8];
int main() {
	freopen("arrangement.in", "r", stdin);
	freopen("arrangement.out", "w", stdout);
	for (int i = 0; i < (1<<8); i++) {
		o[i] = 0;
		for (int j = 0; j < 8; j++)
            if (i & (1<<j))
                o[i]++;
	}
	int t = 0, n, k;
	while(scanf("%d %d", &n ,&k), (n+k)) {
		int S = 0, h = 0;
	    for (int i = 1; i <= n; i++) {
			scanf("%d", &b[i]);
			b[i] -= 25;
			S = S|(1<<b[i]);
			h = max(h, b[i]);
		}
        h++;
        memset(d[0], 0x7f, sizeof(d[0]));
		d[0][0][1<<b[1]][b[1]] = 1;
		d[0][1][0][h]=0;
		int c = 0, p = 0;
		for (int i = 1; i <= n-1; i++) {
			c = p^1;
			memset(d[c], 0x7f, sizeof(d[c]));
			for (int j = 0; j <= k; j++) {
                for (int s = 0; s <= S; s++) {
                    for (int l = 0; l <= h; l++) {
				        if(d[p][j][s][l] == INF)
                            continue;
				        d[c][j][s|(1<<b[i+1])][b[i+1]] = min(
                            d[c][j][s|(1<<b[i+1])][b[i+1]],
                            d[p][j][s][l]+(b[i+1]==l?0:1)
                        );
				        d[c][j+1][s][l] = min(
                            d[c][j][s][l],
                            d[p][j][s][l]
                        );
				    }
			    }
			}
            p = c;
		}
        int ans = INF;
		for (int j = 0; j <= k; j++) {
            for (int s = 0; s <= S; s++) {
                for (int l = 0; l < h; l++) {
    			    if (d[c][j][s][l] == INF)
                        continue;
    			    int t = S^s;
    			    ans = min(ans, d[c][j][s][l]+o[t]);
    		    }
		    }
	    }
        printf("Case %d: %d\n\n", ++t, ans);
	}
	return 0;
}