Online Judge：UVA12235
Label：思维题，状态定义，状压Dp
题面：
题目描述
有一个书架，上面放了n本书，从左往右的第i本书的高度为h[i]。定义书架的混乱度为连续等高段的个数。
例如：{30,30,31,31,32}的混乱度为3；{30,32,32,31}的混乱度为3；{31,32,31,32,31}的混乱度为5。
现在你可以从中抽出至多k本书，然后将他们随意放回书架任意位置，求最终最小的混乱度。
对于100%的数据，N的范围[1,500],K的范围[1,100],书的高度范围[25,32];
输入
第一行两个整数N,K；
第二行，N个元素，表示从左往右每本书的高度。
输出
输出重新摆放K本书的最小混乱度。
"Print a blank line after the output of each case."注意每组数据输出要两个换行！！
样例
Input
5 2
25 25 32 32 25
5 1
25 26 25 26 25
0 0
Output
Case 1: 2
Case 2: 3
题解
发现书的高度只有([25,32])这8种，似乎可以状压的样子。对高度重新编号(0)~(7)方便后面表示，并且称为(8)种不同的颜色。
定义状态(dp[i][j][sta][co])，只考虑前(i)本书，已经将其中(j)本书拿起来了（注意这里是拿起来，其实是采用一种上帝视角，先全部拿出来然后到时候一个一个再放回去），(sta)表示哪些颜色的书还没拿起来过（用二进制表示状态），(co)表示最近一次没拿起来的书的颜色，Dp值表示此时（i及其之前）剩下来没有移动的那些书的混乱度。
然而你会发现直接这样定数组会MLE，如何优化呢，只要你把题解拉下来一点直接看转移过程，就会发现，对于第一维来说每次只用上一层状态，所以可以滚动一下第一维。这样空间就没问题勒。
先来讲讲接下来具体如何实现：
初态：对于任意(h∈[h[1],h[n]]) 有 (dp[i][i-1][1<<h][h])表示，除了当前这本书，前面的(i-1)本书都拿起来时的状态；
终态：统计(dp[n][j][sta][co]+val)的最小值，其中(val)=(all) (Xor) (sta)中1的个数，其实就是那些拿起来的书的颜色种类总数。
而转移呢可以一边读入一边进行。对于当前的高度(h)（先-24转化成0~7中的数字），我们枚举(i,sta,co)，详见下面注释：
inline void Do(int &x,int y){if(x==-1||x>y)x=y;}
//枚举第o本书
int g=0,all=0;
Rep(o,1,n){
//读入高度，预处理下
int h;scanf("%d",&h);h-=25;
//滚动~
g^=1;memset(dp[g],-1,sizeof(dp[g]));
//上面所说的初态初始化。注意要判:o-1<=m，因为第二维我们只开到m的上限100，不特判可能会数组越界
if(o-1<=m)dp[g][o-1][1<<h][h]=1;
//i:已拿个数 s:未选颜色状态 c:最近一次没动的书的颜色
Rep(i,0,min(o,m))Rep(s,1,all)Rep(c,0,7){//枚举上一层状态
if(dp[g^1][i][s][c]==-1)continue;
//最近的位置上有一个跟h颜色相同的书没拿走，很明显把当前这个留下来较优
if(h==c)Do(dp[g][i][s][c],dp[g^1][i][s][c]);
else{
//把当前这个留在原位，由于前面一个跟自己颜色不同，所以混乱值+1
Do(dp[g][i][s|(1<<h)][h],dp[g^1][i][s][c]+1);
//把当前这个拿起来
Do(dp[g][i+1][s][c],dp[g^1][i][s][c]);
}
}
all|=1<<h;//all表示当前已经含有的颜色
}
最后的统计根据上面的终态来就好了。
上完整代码：
#include<bits/stdc++.h>
#define Rep(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
int n,m,dp[2][115][260][10];
inline void Do(int &x,int y){
if(x==-1||x>y)x=y;
}
int main(){
int cas=0;
while(~scanf("%d%d",&n,&m)){
if(n==0||m==0)return 0;memset(dp,-1,sizeof(dp));
int g=0,all=0;
Rep(o,1,n){
int h;scanf("%d",&h);h-=25;
g^=1;memset(dp[g],-1,sizeof(dp[g]));
if(o-1<=m)dp[g][o-1][1<<h][h]=1;
Rep(i,0,min(o,m))Rep(s,1,all)Rep(c,0,7){
if(dp[g^1][i][s][c]==-1)continue;
if(h==c)Do(dp[g][i][s][c],dp[g^1][i][s][c]);
else{
Do(dp[g][i][s|(1<<h)][h],dp[g^1][i][s][c]+1);
Do(dp[g][i+1][s][c],dp[g^1][i][s][c]);
}
}
all|=1<<h;
}
int ans=n;
Rep(i,0,m)Rep(s,1,all)Rep(c,0,7)if(~dp[g][i][s][c]){
int cnt=0,choose=all^s;
Rep(o,0,7)if((1<<o)&choose)cnt++;
ans=min(ans,dp[g][i][s][c]+cnt);
}
printf("Case %d: %d
",++cas,ans);
}
}
End
重新看一遍这道题，难点主要在于正确定义状态。状压、滚动这两个优化根据数据范围和转移过程并不难想。为什么可以以这样的顺序从前到后遍历转移呢，考试的时候也有思考过这样的顺序，但是马上能找到反例——可能前面的书也可以放在他之后的块里。实际上还是没有想通那个上帝视角，即将这些拿出来的书先囤着，到时候一个一个贪心的插♂回去，不急着确定出到底要放在哪个块里。