题目：

BZOJ1939（权限题）

分析：

这题很容易看出是DP，但是状态和转移都不是很好想……

用\(dp[l][r][c]\)表示在\(l\)前面已经新加了\(c\)个和\(l\)一样的弹子时，使区间\([l,r]\)消完所需插入的弹子数量
显然，当\(c\geq k-1\)时，这\(c\)个弹子和\(l\)组成了连续的至少\(k\)个弹子，这些情况是类似的（都可以一次消完）。因此可以用\(c=k-1\)的状态代表所有\(c\geq 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+1\geq k\)时取\(c=k-1\)）
\[dp[l][r][c]=dp[l+1][i-1][0]+dp[i][r][c+1](l+1\leq 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();
}

【BZOJ1939】[Croatian2010] Zuma（动态规划）

原文：https://www.cnblogs.com/zyt1253679098/p/9684107.html