帮助：大毒瘤！！！调了我2h，拍了我2h，最后没调出来，重写才AC。wdnmd。
思路
这题主要是线性 dp ，而状压 dp 只是最后在统计答案时的一个辅助。
首先定义 \(dp[i][j][k]\) 为考虑前 \(i\) 本书，已经抽出来了 \(j\) 本，最后没被抽出来的一本书是高度 \(k\) 的最小混乱度。
每次放入的书与最后一位不同的时候我们把答案 \(+1\) 。
但是这样有一个弊端，就是当我们取出一些书后，还要放回去。我们自然是要放到那些没拿出来的同高度的书里面，但是如果一种高度的书全拿出来了，我们就必须加上那些全拿出来的书的种数。
观察到书本高度只能在 \([25,32]\) 这个区间里，有 \(8\) 种高度，所以我们考虑把所有书的高度 \(-25\) 后状压。
重新定义 \(dp[i][j][k][l]\) 表示考虑前 \(i\) 本书，已经抽出来 \(j\) 本，此时没被拿出来的书的状态为 \(k\) ，放在书架里的最后一本书的类型为 \(l\) 时的最小混乱度。
于是可以分两种情况转移：
- 对于不把这本书拿出来的情况：
这里 \(k|(a[i])\) 的原因是要把它放进去。后面 \((a[i]!=l)\) 的原因是如果高度不同，混乱度要 \(+1\) 。
- 对于把这本书拿出来的情况：
在 dp 完成之后，我们最后枚举后三维，并且让最终状态 \(((st \oplus p)\&p)\) ，就可以求出书架里少了哪些书，把少的书的个数加上即可，最后求个 \(\min\) 。注意提前预处理出每个二进制数 \(1\) 的个数减小常数。
最后观察到空间开销大，并且每次转移只会用到 \(i-1\) 里的数，所以考虑滚动数组优化 dp 。
同时注意提前把不合法的情况排除掉，可以减小部分常数。
代码
#include <bits/stdc++.h>
using namespace std;
int dp[2][105][260][15],a[105],pre[260],n,m,p,ans,now=0;
void solve()
{
ans=0x3f3f3f3f;
memset(dp,0x3f,sizeof(dp));
dp[0][0][0][8]=0;
for(int i=1;i<=n;i++)
{
int ni=(i&1),lst=(ni^1);
memset(dp[ni],0x3f,sizeof(dp[ni]));
for(int j=0;j<=m;j++)
{
for(int k=0;k<=p;k++)
{
for(int l=0;l<=8;l++)
{
if(dp[lst][j][k][l]>=(0x3f3f3f3f/2))continue;
dp[ni][j][(k|(1<<a[i]))][a[i]]=min(dp[ni][j][(k|(1<<a[i]))][a[i]],dp[lst][j][k][l]+(a[i]!=l));
dp[ni][j+1][k][l]=min(dp[ni][j+1][k][l],dp[lst][j][k][l]);
}
}
}
}
for(int i=0;i<=m;i++)
{
for(int j=0;j<=p;j++)
{
for(int k=0;k<=8;k++)
{
ans=min(ans,dp[(n&1)][i][j][k]+pre[(j^p)&p]);
}
}
}
printf("Case %d: %d\n\n",now,ans);
}
int main()
{
for(int i=0;i<(1<<8);i++)
{
for(int j=0;j<8;j++)
{
pre[i]+=((i>>j)&1);
}
}
while(1)
{
now++;
scanf("%d %d",&n,&m);
if(n==0&&m==0)break;
p=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]-=25;
p=(p|(1<<a[i]));
}
solve();
}
return 0;
}