记录编号	319487	评测结果	AWWWWWWWWW
题目名称	993.[NOIP 2010冲刺三]宁采臣的书架	最终得分	10
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	1.265 s
提交时间	2016-10-10 18:23:49	内存使用	2.08 MiB

//KZNS
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define Nmax 102
#define INF 1061109567
int N, K;
int ls[Nmax] = {0};
int v[Nmax] = {0};
int nb = 0;
int S;
int H;
void init() {
    memset(v, 0, sizeof(v));
    H = 0;
    for (int i = 0; i < N; i++) {
        scanf("%d", ls+i);
        ls[i] -= 25;
        S |= 1<<ls[i];
        v[i] = 1;
        H = max(H, ls[i]);
    }
    nb = N;
    H++;
}
int OOO[256] = {0};
int F[2][Nmax][256][9];
void work() {
    memset(F, 63, sizeof(F));
    int c = 1, p = 0;
	F[p][0][(1<<ls[1])][ls[0]] = 1;
	if (v[0] <= K)
	   F[p][v[0]][0][H] = 0;
	for (int i = 0; i < N-1; i++) {
		memset(F[c], 63, sizeof(F[c]));
		for (int j = 0; j <= K; j++) {
            for (int s = 0; s < S; s++) {
                for (int l = 0; l <= H; l++) {
			        if (F[p][j][s][l] == INF)
                        continue;
			        F[c][j][s|(1<<ls[i+1])][ls[i+1]] = min(
                        F[c][j][s|(1<<ls[i+1])][ls[i+1]],
                        F[p][j][s][l] + (ls[i+1]==l?0:1)
                    );
			        F[c][j+1][s][l] = min(
                        F[c][j][s][l],
                        F[p][j][s][l]
                    );
			    }
		    }
	    }
        p = c;
        c ^= 1;
	}
    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 (F[c][j][s][l] == INF)
                    continue;
		        int t = S^s;
	            ans = min(ans, F[c][j][s][l]+OOO[t]);
	        }
	    }
	}
    printf("%d\n", ans);
}
int main() {
    freopen("arrangement.in", "r", stdin);
    freopen("arrangement.out", "w", stdout);
    int u;
    for (int i = 0; i < 256; i++) {
        u = i;
        while (u) {
            OOO[i]++;
            u ^= (u&-u);
        }
    }
    scanf("%d %d", &N, &K);
    int T = 1; 
    while (N || K) {
        init();
        printf("Case %d: ", T++);
        work();
        printf("\n");
        scanf("%d %d", &N, &K);
    }
    return 0;
}
//UBWH