2014
03-09

# Help Bubu

Bubu’s bookshelf is in a mess! Help him!

There are n books on his bookshelf. We define the mess value to be the number of segments of consecutive equal-height books. For example, if the book heights are 30, 30, 31, 31, 32, the mess value is 3, that of 30, 32, 32, 31 is also 3, but the mess value of 31, 32, 31, 32, 31 is 5 – it’s indeed in a mess!

Bubu wants to reduce the mess value as much as possible, but he’s a little bit tired, so he decided to take out at most k books, then put them back somewhere in the shelf. Could you help him?

There will be at most 20 test cases. Each case begins with two positive integers n and k (1 <= k <= n <= 100), the total number of books, and the maximum number of books to take out. The next line contains n integers, the heights of each book, from left to right. Each height is an integer between 25 and 32, inclusive. The last test case is followed by n = k = 0, which should not be processed.

There will be at most 20 test cases. Each case begins with two positive integers n and k (1 <= k <= n <= 100), the total number of books, and the maximum number of books to take out. The next line contains n integers, the heights of each book, from left to right. Each height is an integer between 25 and 32, inclusive. The last test case is followed by n = k = 0, which should not be processed.

5 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0

Case 1: 2

Case 2: 3

<= 100

那我们要怎么表示抽走的状态呢？压缩成一个数字吗？不行，还必须和k扯上关系，也就是说必须有一维表示数量，而抽走书的种类可以用总状态减去留下来的状态来表示。这样就可以用dp[i][j][k][s]来进行状态转移，dp[i][j][k][s]表示到第i本书时取走j本书留下来的书状态为k最后一本书高度为s。状态转移见代码。复杂度O（n*k*(1<<8)*8)。

5 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0

#include <stdio.h>
#include <string.h>
#define MIN 110
#define INF 1047483647
#define min(a,b) (a)<(b)?(a):(b)

int n,m,ht[MIN],ans,one[1<<8]; //one[i]表示状态i中1的个数
int state,dp[2][MIN][1<<8][10];//dp[i][j][k][s]表示到第i行取走j本书剩下的状态数为k最后一本书高度是s时最少连续段数

void Initial() {

for (int i = 0; i < (1<<8); ++i) {

for (int j = 0; j < 8; ++j)
if (i & (1<<j)) one[i]++;
}
}

int main()
{
int i,j,k,s,cas = 0;
int pre,cur,mx,tot;
Initial();

while (scanf("%d%d",&n,&m) ,n+m) {

mx = state = 0;
for (i = 1; i <= n; ++i) {

scanf("%d",&ht[i]);
ht[i] -= 25;
if (ht[i] > mx) mx = ht[i];       //统计最大的高度
state |= (1<<ht[i]);
}

//Initial
mx++ ,tot = (1<<mx);
for (j = 0; j <= m; ++j)
for (k = 0; k < tot; ++k)
for (s = 0; s <= mx; ++s)
dp[1][j][k][s] = INF;

dp[1][0][1<<ht[1]][ht[1]] = 1;   //如果第一本书留下来段数就为1
dp[1][1][0][mx] = 0;             //mx其实是不存在的高度，因为第一本书被拿走了那么留下的最后一本书高度实际是不存在的，用这个只是好转移
for (i = 2; i <= n; ++i) {

cur = i & 1;                 //当前状态
pre = 1 - cur;               //前一个状态

for (j = 0; j <= m ; ++j)
for (k = 0; k < tot; ++k)
for (s = 0; s <= mx; ++s)
dp[cur][j][k][s] = INF;

for (j = 0; j <= m && j < i; ++j)
for (k = 0; k < tot; ++k)
for (s = 0; s <= mx; ++s) {

if (dp[pre][j][k][s] == INF) continue;           //小剪枝，但不剪就TLE
int stk = k | (1<<ht[i]);                        //当前的状态
if (j < m)                                      //如果还可以取走
dp[cur][j + 1][k][s] = min(dp[cur][j + 1][k][s], dp[pre][j][k][s]);
if (s == ht[i])                                 //如果和留下来的最后一本高度相同，则当前的书留下来并不增加段数
dp[cur][j][k][s] = min(dp[cur][j][k][s],dp[pre][j][k][s]);
else                                            //增加一段
dp[cur][j][stk][ht[i]] = min(dp[cur][j][stk][ht[i]],dp[pre][j][k][s]+1);
}
}

cur = n & 1,ans = n;
for (j = 0; j <= m; ++j)
for (k = 0; k < tot; ++k)
for (s = 0; s < mx; ++s)
if (dp[cur][j][k][s] != INF) {

int st = state ^ k;
ans = min(ans,one[st]+dp[cur][j][k][s]);
}

printf("Case %d: %d\n\n",++cas,ans);
}
}