题意
有一个长为 \(n\) 的序列 \(a\)，你可以选择一个数，将它放到任意位置，共可以操作 \(m\) 次。
我们定义 \(w\) 表示不同连续段的个数，问 \(k\) 次操作后，\(w\) 的最小值是多少？
\(n,m\le 500\)， \(25\le a_i\le 32\)
思路
\(a_i\) 的范围很小，提示我们向状态压缩方面想。
这道题，无非就是考虑一个数选不选出来：如果选出来，那么一定是放到一个与它相同，且没有动过的数旁边；如果不选出来，那么就看序列的末尾与它是否相同。
因此我们可以考虑设计一个状态 \(f_{i,j,k,s}\) 为最小段数，表示当前考虑到第 \(i\) 个数，操作了 \(j\) 次，当前序列末尾的数为 \(k\)；\(s\) 则是状压，第 \(x\) 位为 \(1\) 当且仅当 \(i\) 及以前的 \(x\) 都被选出来操作。
因此我们可以考虑转移：
- \(a_i\) 选出来，从 \(f_{i-1, j-1, k, s}\) 转移过来：
-
如果在此之前 \(a_i\) 都没出现过，显然 \(s\) 上第 \(a_i\) 位是 \(0\)，这时要加上 \(2^{a_i}\)，设新状态为 \(ns\)。
- \[f_{i,j,k,ns}\leftarrow f_{i-1,j-1,k,s} \]
- \(a_i\) 保持不动从 \(f_{i-1, j, k, s}\) 转移过来：
-
如果 \(s\) 的 \(a_i\) 位上为 \(1\)，我们要将它改为 \(0\)，因为有不动的 \(a_i\) 了。
- \[f_{i,j,a_i,ns}\leftarrow f_{i-1,j,k,s} \]
一些细节可见代码。
代码
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
int sign = 1, re = 0; char c = getchar();
while(!isdigit(c)) {if(c == '-') sign = -1; c = getchar();}
while(isdigit(c)) {re = re * 10 + (c - '0'); c = getchar();}
return sign * re;
}
inline void cxkmin(int &a, int b) {a = a > b ? b : a;}
const int S = (1 << 8) - 1;
int n, m, a[505];
int f[2][101][8][1 << 8];
bitset<8> vis;
signed main()
{
freopen("book.in", "r", stdin);
freopen("book.out", "w", stdout);
n = rd(), m = rd();
FOR(i, 1, n) a[i] = rd() - 25;
memset(f[0], 0x3f, sizeof(f[0]));
int pres = 0;
FOR(i, 1, n)
{
int now = i & 1, la = now ^ 1;
memset(f[now], 0x3f, sizeof(f[now]));
FOR(j, 1, m) FOR(k, 0, 7) FOR(x, 0, S) if(f[la][j - 1][k][x] != 0x3f3f3f3f)
{
int nx = x;
if(!(x & (1 << a[i])) && !vis[a[i]]) nx ^= (1 << a[i]);
cxkmin(f[now][j][k][nx], f[la][j - 1][k][x]);
}
FOR(j, 0, m) FOR(k, 0, 7) FOR(x, 0, S) if(f[la][j][k][x] != 0x3f3f3f3f)
{
int nx = x;
if(x & (1 << a[i])) nx ^= (1 << a[i]);
cxkmin(f[now][j][a[i]][nx], f[la][j][k][x] + (k != a[i]));
}
vis[a[i]] = 1;
if(i - 1 <= m) cxkmin(f[now][i - 1][a[i]][pres], 1);
pres |= 1 << a[i];
}
int ans = 0x3f3f3f3f;
FOR(j, 0, m) FOR(k, 0, 7)
cxkmin(ans, f[n & 1][j][k][0]);
printf("%d", ans);
return 0;
}