题目大意
Elly有一排$n$颗珍珠（$1 leq n leq 1000$）。每颗珍珠的颜色是$m$种不同的颜色的其中一种（$1 leq m leq 15$），第$i$颗珍珠的颜色是$a[i]$。现在她想让颜色相同的珍珠要排在相邻，最终配置中颜色的顺序并不重要。必须移动的珍珠数量是多少才能按颜色分组？（移动珍珠意味着将它从行中取出然后将其插回任意位置——在任何两个珍珠之间或在所有珍珠之前或之后。）
题解
因为我们把珍珠取出来后就可以插入任意位置，所以我们可以排好后再插入，也就是我们并不需要管取出后的珍珠，只需要考虑取出哪些珍珠。
我们设$dp[i][S]$表示前$i$颗珍珠中，所有珍珠的颜色都在集合$S$内的最少需要取出的珍珠数量。
容易想到。当$a[i] otin S$时，有
$$dp[i][S] = dp[i - 1][S] + 1$$
而当$a[i] in S$时，此时第$i$颗珍珠要么保留，要么也要取出。
如果取出的话，那还是之前的状态转移方程
$$dp[i][S] = dp[i - 1][S] + 1$$
如果保留的话，那我们要枚举$j in [1,i]$，在$[1,j)$的范围内集合为$S - S_{a[i]}$的情况，这里已经用$dp[j - 1][S - S_{a[i]}]$记录了；在$[j,i]$的范围内集合仍为$S$。
当$a[i] ot = a[j]$时，显然第$j$颗珍珠要取出。这里我们用$Count(j,i)$，表示$[j,i]$中要取出的珍珠数量。
当$a[i] = a[j]$时，则有状态转移方程
$$dp[i][S] = dp[j - 1][S - S_{a[i]}] + Count(j, i)$$
综合两种情况，可以得到最终的状态转移方程为
$$dp[i][S] = egin{cases} dp[i - 1][S] + 1 &a[i] otin S \ min {dp[i - 1][S] + 1, underset{1 leq j leq i}{min} { dp[j - 1][S - S_{a[i]}] + Count(j, i) } } &a[i] in S end{cases}$$
此时的时间复杂度为$O(2^{m} n^{2})$，还是TLE。
实际上我们只需要记录有关$j$部分的前缀最小值，就能省去枚举$j$的循环，时间复杂度降为$O(2^{m}n)$，具体细节看下面的代码。
#include <iostream> #include <cstring> #define MAX_N (50 + 5) #define MAX_M (15 + 5) #define MAX_S ((1 << 15) + 5) using namespace std; int n, m; int a[MAX_N]; int sum[MAX_M][MAX_N]; int dp[MAX_N][MAX_S], mdp[MAX_M][MAX_S], l[MAX_M][MAX_S]; int main() { cin >> n >> m; for(int i = 1; i <= n; ++i) { cin >> a[i]; } memset(dp, 0x3f, sizeof dp); memset(mdp, 0x3f, sizeof mdp); const int lim = (1 << m) - 1; for(int c = 1; c <= m; ++c) { for(int i = 1; i <= n; ++i) { sum[c][i] = sum[c][i - 1]; if(a[i] != c) ++sum[c][i]; } } for(int s = 0; s <= lim; ++s) { dp[0][s] = 0; } for(int i = 1; i <= n; ++i) { dp[i][0] = i; } int p; for(int s = 1; s <= lim; ++s) { for(int i = 1; i <= n; ++i) { p = 1 << a[i] - 1; dp[i][s] = dp[i - 1][s] + 1; if(s & p) { mdp[a[i]][s] = min(mdp[a[i]][s] + sum[a[i]][i] - sum[a[i]][l[a[i]][s]], dp[i - 1][s - p]); dp[i][s] = min(dp[i][s], mdp[a[i]][s]); l[a[i]][s] = i; } } } cout << dp[n][lim]; return 0; }
毒瘤区赛，毒瘤出题人