难点在于状态设计，从左向右一本书一本书的考虑，每本书的决策有两种拿走或者留下，
对于拿走后的书，之后要放回，但是决策过程中不知道到往哪里放，
虽然前面的书的种类确定，可能是往后面放更优，而后面的书的类型还不确定。对于所有拿出来的书，最后会增加多少段只和书的种类有关。
所以我们用s记录留下书的种类，等到所有书都考虑完了以后一并放回。
对于留下的书，是否成为新的一段和上一次书的高度有关，因此用一个last记录上一次书的种类。（用s来判断一下last不存在的情况）
dp[i = 第i本书][j = 拿了j次][s = 剩下书的种类][last = 上一次书的种类] = 最小混乱度
转移方程见代码
直接for是最好写的
#include<bits/stdc++.h> using namespace std; const int maxn = 101, maxs = 1<<8; int dp[2][maxn][maxs][8]; int bc[maxs]; int h[maxn]; const int INF = 0x3f3f3f3f; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif for(int i = maxs; i-- ;){ int x = i; while(x){; bc[i] += x&1; x >>= 1; } } int ks = 0, n, k; while(scanf("%d%d",&n,&k),n+k){ int All = 0; for(int i = 0; i < n; i++){ scanf("%d",h+i); h[i] -= 25; All |= 1<<h[i]; } memset(dp[0],0x3f,sizeof(dp[0])); dp[0][0][1<<h[0]][h[0]] = 1; dp[0][1][0][0] = 0; for(int i = 1; i < n; i++){ int a = i&1, b = a^1, bs = 1<<h[i]; memset(dp[a],0x3f,sizeof(dp[a])); for(int j = k; j >= 0; j--){ for(int s = maxs; s--; ){ for(int ls = 8; ls--; ){ if(dp[b][j][s][ls] < INF){ dp[a][j][s|bs][h[i]] = min(dp[a][j][s|bs][h[i]], dp[b][j][s][ls] + (s?( h[i] == ls?0:1 ):1)); if(j < k) dp[a][j+1][s][ls] = min(dp[a][j+1][s][ls], dp[b][j][s][ls]); } } } } } int a = n&1^1; int ans = n+1; for(int s = maxs; s--;){ for(int ls = 8; ls--; ){ ans = min(ans, dp[a][k][s][ls] + bc[All^s]); } } printf("Case %d: %d ",++ks,ans); } return 0; }
实际上可能有很多状态访问不到的时候，for会枚举到一些无用的状态，这时候可以考虑把有效的状态保存下来，（记忆化搜索也可以避免访问无用状态，但是没办法用滚动数组了）
这样的话不需要对整个dp数组初始化，取代的是需要状态判重。
这样写有种做搜索题的感觉。
#include<bits/stdc++.h> using namespace std; const int maxn = 101, maxs = 1<<8; int dp[2][maxn][8][maxs]; int vis[maxn][8][maxs],clk; int h[maxn]; const int nil = 0; struct state { int ct,ls,s; }vc[2][maxn*8*maxs]; int sz[2]; #define dim(x) [x.ct][x.ls][x.s] #define add(id,ct,ls,s) vc[id][sz[id]++] = state{ct,ls,s}; #define psb(id) vc[id][sz[id]++] = y; #define clr(id) sz[id] = 0; #define edof(id) vc[id][sz[id]] #define updata(v) if(vis Td != clk){ vis Td = clk; dp[a] Td = v; psb(a); }else { dp[a] Td = min(dp[a] Td, v); } inline int bc(int x) { int re = 0; while(x){ re += x&1; x >>= 1; } return re; } //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int ks = 0, n, k; while(scanf("%d%d",&n,&k),n+k){ int All = 0; for(int i = 0; i < n; i++){ scanf("%d",h+i); h[i] -= 25; All |= 1<<h[i]; } clr(0); state y = {0,h[0],1<<h[0]}; dp[0] dim(y) = 1; psb(0) y = {1,nil,0}; dp[0] dim(y) = 0; psb(0) for(int i = 1; i < n; i++){ int a = i&1, b = a^1, bs = 1<<h[i]; clr(a) clk++; for(int j = 0; j < sz[b]; j++){ auto &x = vc[b][j]; int val = dp[b] dim(x); int tmp = val + ( x.s? ( (x.ls == h[i])?0:1 ) : 1 ); y = {x.ct,h[i],x.s|bs}; #define Td [y.ct][y.ls][y.s] updata(tmp) if(x.ct < k){ y = {x.ct+1, x.ls, x.s}; updata(val) } } } int a = n&1^1; int ans = n+1; for(int j = 0; j < sz[a]; j++){ auto &x = vc[a][j]; ans = min(ans, dp[a] dim(x) + bc(All^x.s)); } printf("Case %d: %d ",++ks,ans); } return 0; }