记录编号	319421	评测结果	WWEEEEEEEE
题目名称	993.[NOIP 2010冲刺三]宁采臣的书架	最终得分	0
用户昵称	KZNS	是否通过	未通过
代码语言	C++	运行时间	1.529 s
提交时间	2016-10-10 17:31:32	内存使用	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;
void init() {
    int u;
    int l;
    scanf("%d", &l);
    ls[nb] = l - 25;
    v[nb]++;
    S |= (1<<ls[nb]);
    for (int i = 1; i < N; i++) {
        scanf("%d", &u);
        if (u == l) {
            v[nb]++;
        }
        else {
            nb++;
            l = u;
            ls[nb] = l - 25;
            S |= (1<<ls[nb]);
            v[nb]++;
        }
    }
    nb++;
}
int OOO[256] = {0};
int F[2][Nmax][256][9];
void work() {
    memset(F, 63, sizeof(F));
    int lt = 0, nw = 1;
    F[lt][0][1<<ls[nb]][ls[0]] = 1;
    if (v[0] <= K)
        F[lt][v[0]][0][8] = 0;
    for (int i = 0; i < nb-1; i++) {
        memset(F[nw], 63, sizeof(F[nw]));
        for (int j = 0; j <= K; j++) {
            for (int k = 0; k < 256; k++) {
                for (int e = 0; e < 9; e++) {
                    if (F[lt][j][k][e] == INF)
                        continue;
                    F[nw][j][k|(1<<ls[i+1])][ls[i+1]] = min(
                        F[nw][j][k|(1<<ls[i+1])][ls[i+1]],
                        F[lt][j][k][e] + (e == ls[i] ? 0 : 1)
                    );
                    if (j + v[i+1] <= K) {
                        F[nw][j+v[i+1]][k][e] = min(
                            F[nw][j+v[i+1]][k][e],
                            F[lt][j][k][e]
                        );
                    }
                }
            }
        }
        lt = nw;
        nw ^= 1;
    }
    int ans = INF;
    for (int j = 0; j <= K; j++) {
        for (int k = 0; k < 256; k++) {
            for (int e = 0; e < 8; e++) {
                if (F[lt][j][k][e] == INF)
                    continue;
                ans = min(ans, F[lt][j][k][e] + OOO[S^j]);
            }
        }
    }
    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