Description
对于一个数列，其混乱度定义为连续相等的数的段数。如：1 2 1 2 1，其混乱度为5，而：1 2 2 3 3，其混乱度为3。现给出一个数列，允许取出k个数并允许插入数列中的任意一个位置，要求该数列的混乱度尽量小，并求出这个最小混乱度。
对于100%的数据：1 <= k <= n <= 100，所有数均在[25，32]内。
Solution
由于取出一个数i，你可以放在左边和右边，你不知道放在哪里才是最优的？
那么我们可以直接把要取的全部取出来，最后再插进数列中。
设F[i][j][k][s]表示做到第i个数，当前数列最后的数为j，取出了k个数，当前数列中数的集合为s的最小混乱度。
转移很简单：
1、第i+1个数取出：F[i+1][j][k+1][s] = min(F[i+1][j][k+1][s], F[i][j][k][s]);
2、第i个数放在最后面：F[i+1][a[i+1]][k][s|(1<<i)] = min(F[i+1][a[i+1]][k][s|(1<<i)], F[i][j][k][s]+(a[i+1] != j));
最后只需要把最后状态没有出现的数集合算上就好。
Code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm> using namespace std; #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define mset(a, b) memset(a, b, sizeof(a))
int n, lim, a[];
int f[][][][<<];
int s_cnt;
bool vis[]; void Ckmin(int &AI, const int &BI) { if (AI > BI) AI = BI; } int calc(int x)
{
int t_cnt = ;
while (x > )
{
if (x&) t_cnt ++;
x >>= ;
}
return s_cnt-t_cnt;
} int main()
{
scanf("%d %d", &n, &lim);
REP(i, , n) scanf("%d", &a[i]), a[i] -= ;
REP(i, , n) if (!vis[a[i]]) vis[a[i]] = , s_cnt ++;
REP(i, , n)
REP(j, , )
REP(k, , lim)
REP(s, , (<<)-) f[i][j][k][s] = ;
f[][][][] = ;
REP(i, , n-)
REP(j, , )
REP(k, , lim)
REP(s, , (<<)-)
if (f[i][j][k][s] < )
{
if (s&(<<a[i+]))
{
if (j == a[i+]) Ckmin(f[i+][j][k][s], f[i][j][k][s]);
else
{
if (k < lim) Ckmin(f[i+][j][k+][s], f[i][j][k][s]);
Ckmin(f[i+][a[i+]][k][s], f[i][j][k][s]+);
}
}
else
{
if (k < lim) Ckmin(f[i+][j][k+][s], f[i][j][k][s]);
Ckmin(f[i+][a[i+]][k][s|(<<a[i+])], f[i][j][k][s]+);
}
}
int ans = ;
REP(j, , )
REP(k, , lim)
REP(s, , (<<)-)
Ckmin(ans, f[n][j][k][s]+calc(s));
printf("%d\n", ans);
return ;
}