依舊是先寫部落格打草稿再寫碼，聽過題解後來整理一下思路，我們把抽出插入分為兩個部分，①抽出k個手辦，②将k個手辦插入剩餘（n-k）的手辦堆中。
問題二很好解決，隻要插入的堆中有一樣高度的手辦，就不會改變混亂值，盡量把這個手辦安排在隊列最後就不會影響到前面的排列，總體來說就是個貪心的思路。
問題一是難點，前n個手辦抽出k個每個手辦的狀态隻有取（1）或者不取（0）兩種狀态，這聽起來就很01背包了，對于第i個手辦，抽出時是否影響到整體混亂度取決于末位（前一位）的高度(last)（我們從前往後取），這是需要記錄的，然後因為要限制隻抽出k個，是以我們可以記錄一下現在已經取了幾個手辦(j)了，一如平時我們解01背包那樣。但是僅僅如此隻會讓第二問顯得更麻煩，如果我能知道剩餘有哪些手辦了就好了，我們因為總共隻有八種狀态，是以可以狀态壓縮來表示目前狀态(status)，用一串二進制的1和0表示目前位是否存在。
我們讓dp[i][j][status][last]來表示取了目前第i位，這是第j次取，它的上一位是last，此時剩餘元素中存在的狀态是status時的最小混亂值。
之前提到的抽出時是否影響到整體混亂度取決于末位，就是說有這樣的關系，設我們目前輸入的手辦高度為x，那麼
if(last == x) dp[i][j][status][last] = min (dp[i][j][status][last], dp[i - 1][j][status][last]);
目前高度與上一次高度一緻的話，肯定是不取最好嘛。
如果不一緻呢？就要讨論是取還是不取了。
不取，就意味着要合并狀态：
dp[i][j][status|(1<<x)][x] = //目前不取了，j維持不變，status合并，更新末位
min (dp[i][j][status|(1<<x)][x], //在本身和i-1位時就已經取了j個，那時status和last的狀态比較，
dp[i-1][j][status][last] + 1); //因為last!=x，是以混亂度必+1
那麼取的話是什麼情況呢？
dp[i][j+1][status][last] = min (dp[i][j+1][status][last], dp[i-1][j][status][last]);
//單純取最小值，因為statu和last啥都沒改變
那麼核心動态轉移方程就出來了
if(last == x)
dp[i][j][status][last] = min (dp[i][j][status][last], dp[i - 1][j][status][last]);
else
{
dp[i][j][status|(1<<x)][x] = min (dp[i][j][status|(1<<x)][x], dp[i-1][j][status][last] + 1);
dp[i][j+1][status][last] = min (dp[i][j+1][status][last], dp[i-1][j][status][last]);
}
做到這裡我已經大呼大佬們的神乎其技了，這個轉移方程出來之後基本上就能做了，不過為了保險起見怕空間炸還需要用滾動數組優化一下。我不知道為啥一開始交的沒有優化的代碼沒有mle而是wa了，其他的改動也不多，大概是寫挂了。
滾動數組：因為轉移方程中我們發現dp[i][][][]的狀态隻與dp[i - 1][][][]的狀态有關，是以我們隻需要開一個大小為2的數組作第一維，每一次循環開始時先把不用的那輪初始化，然後用其記錄本輪的狀态，每次用0和1表示這一輪和下一輪的關系即可，具體操作見代碼。說起來一直以來用的
#define inf 2147483647
的inf來初始化代碼在這裡竟然炸了，就很奇怪，後來退而求其次拿了平時經常模的
#define hrdg 1000000007
就過了，果然模hrdg能過代碼。
再來講講第二個問題，我們得到了所有的dp[n%2][][][]時的最小混亂值，插回去的話，我們需要先統計一遍原本有多少種高度，如果目前status（剩餘手辦高度的狀态）的高度種類比總共高度少，那麼插回去就會增加混亂值。可以用預處理，計算出從0到(1<<8)-1所有手辦的情況時有多少種類存在num[ ]數組裡，然後每一次讀入循環的答案統計一次tot表示全部種類數
ans = hrdg;
for (int j = 0; j <= k; j++)
{
for (int status = 0; status <= all; status++)
{
for (int last = 0; last <= 8; last++)
{
if(dp[n%2][j][status][last] != hrdg)
ans = min(ans, dp[n%2][j][status][last]+tot-num[status]);
}
}
}
完整AC代碼如下：
#include<bits/stdc++.h>
#define FOR(a, b, c) for(int a=b; a<=c; a++)
#define maxn 105
#define maxm 55
#define hrdg 1000000007
#define inf 2147483647
#define llinf 9223372036854775807
#define ll long long
#define pi acos(-1.0)
#define ls p<<1
#define rs p<<1|1
using namespace std;
int n, k, x, dp[2][maxn+5][1<<8+1][10], ans, cnt;
int all, tot, num[1<<9+1], now;
bool vis[9];
inline int read(){
char c=getchar();long long x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int gkd(int x){
int ret = 0;
while(x)
{
if(x&1)
ret++;
x >>= 1;
}
return ret;
}
int main()
{
for (int i = 0; i <= 1<<8; i++)
num[i] = gkd(i); //預處理num[]數組
while (~scanf("%d %d", &n, &k))
{
cnt++;
if(n == 0 && k == 0)
break;
memset(vis, 0, sizeof(vis));
memset(dp[0], hrdg, sizeof(dp[0])); //為什麼我用2147483647初始化會爆掉啊？？
dp[0][0][0][8] = 0;
all = 0; tot = 0; //循環初始化
for (int i = 1; i <= n; i++)
{
x = read();
x -= 114514;
all |= 1 << x;
now = i % 2;
if(vis[x] == 0)
{
vis[x] = 1;
tot++;
}
memset(dp[now], hrdg, sizeof(dp[now])); //初始化上上次的狀态，因為這沒什麼用
for (int j = 0; j <= min(k, i); j++)
{
for (int status = 0; status <= all; status++)
{
for (int last = 0; last <= 8; last++)
{
if(dp[!now][j][status][last] != hrdg) //核心轉移方程如下
{
if(last == x)
dp[now][j][status][last] = min (dp[now][j][status][last], dp[!now][j][status][last]);
else
{
dp[now][j][status|(1<<x)][x] = min (dp[now][j][status|(1<<x)][x], dp[!now][j][status][last] + 1);
dp[now][j+1][status][last] = min (dp[now][j+1][status][last], dp[!now][j][status][last]);
}
}
}
}
//puts("");
}
}
//printf("%d\n", all);
ans = hrdg;
for (int j = 0; j <= k; j++)
{
for (int status = 0; status <= all; status++)
{
for (int last = 0; last <= 8; last++)
{
if(dp[n%2][j][status][last] != hrdg)
ans = min(ans, dp[n%2][j][status][last]+tot-num[status]); //更新答案
}
}
}
printf("Case %d: %d\n", cnt, ans);
}
return 0;
}
/*
9 6
114518 114520 114514 114520 114515 114521 114515 114519 114516
3 1
114516 114514 114518
2 2
114521 114521
6 3
114515 114520 114521 114518 114521 114515
0 0
*/