题目：
BZOJ1939（权限题）
分析：
这题很容易看出是DP，但是状态和转移都不是很好想……
用(dp[l][r][c])表示在(l)前面已经新加了(c)个和(l)一样的弹子时，使区间([l,r])消完所需插入的弹子数量
显然，当(cgeq k-1)时，这(c)个弹子和(l)组成了连续的至少(k)个弹子，这些情况是类似的（都可以一次消完）。因此可以用(c=k-1)的状态代表所有(cgeq k-1)的状态。
对于状态((l,r,k-1))，(l)可以和前面(k-1)个同色弹子一起消掉，因此只需要考虑要插入多少个才能完全消掉区间([l+1,r])。这就得到第一个转移：（因为([l+1,r])紧贴着(l)，(l+1)左侧没有新插入的弹子，所以消掉([l+1,r])所需插入的弹子数就是(dp[l+1][r][0])）
[dp[l][r][k-1]=dp[l+1][r][0]
]
对于状态((l,r,c))，在前面插入一个(l)的同色弹子就变成了((l,r,c+1))，所以比消完((l,r,c+1))状态多一步，即：
[dp[l][r][c]=dp[l][r][c+1]+1
]
考虑对于弹子(l) ，除了在它前面加((k-1))个同色弹子外，还可以找一个弹子(i(i>l,a_l=a_i))，先消去区间([l+1,i-1])（该区间可能不存在），这样(i)左侧就有((c+1))个同色弹子，这就是状态((i,r,c+1))。由此得到第三个转移：（注意特判(l+1=i)时状态((l+1,i-1,0))不存在，以及(c+1geq k)时取(c=k-1)）
[dp[l][r][c]=dp[l+1][i-1][0]+dp[i][r][c+1](l+1leq i-1)
]
[dp[l][r][c]=dp[i][r][c+1](l+1=i)
]
代码：
有了DP方程以后代码还是很好写的
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
namespace zyt
{
const int N = 110, K = 7;
int arr[N], dp[N][N][K];
int work()
{
int n, k;
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> arr[i];
for (int i = 0; i < n; i++)
for (int c = 0; c < k; c++)
dp[i][i][c] = k - c - 1;
for (int len = 2; len <= n; len++)
for (int l = 0; l + len - 1 < n; l++)
{
int r = l + len - 1;
for (int c = k - 1; c >= 0; c--)
{
if (c < k - 1)
dp[l][r][c] = dp[l][r][c + 1] + 1;
else
dp[l][r][c] = dp[l + 1][r][0];
if (arr[l] == arr[l + 1])
dp[l][r][c] = min(dp[l][r][c], dp[l + 1][r][min(k - 1, c + 1)]);
for (int i = l + 2; i <= r; i++)
if (arr[l] == arr[i])
dp[l][r][c] = min(dp[l][r][c], dp[l + 1][i - 1][0] + dp[i][r][min(k - 1, c + 1)]);
}
}
cout << dp[0][n - 1][0];
return 0;
}
}
int main()
{
return zyt::work();
}