题解：P12189 [蓝桥杯 2025 省 Java A/研究生组] 甘蔗

· · 题解

题目传送门

思路

最优化问题，考虑动态规划。

我们发现 n,m 和值域很小，不妨考虑二维 dp，设 dp_{i,j} 为将第 i 个甘蔗高度变为 j 时的最小代价。

接下来考虑初始化，显然 |a_i-a_{i+1}| 这个条件对于 dp_{1,i} 来说并不受约束，直接令 dp_{1,i}=[i<a_1] 即可。

接下来考虑状态转移。由于是二维，我们肯定要枚举一个 j 从 0\to a_i，然后要枚举 i-1 位填的 k 从 0\to a_{i-1}，开个布尔数组 O(1) 判断 |j-k|\in B，然后状态转移：

dp_{i,j}=\min_{k=0,|j-k|\in B}^{a_{i-1}}\{dp_{i-1,k}+[j<a_i]\}

这样做的复杂度是 O(nN^2)，其中 N 是值域。

虽然足以通过，但我们还可以继续优化复杂度。观察数据范围，我们发现 n,m<N，不妨考虑将第三维 k 的枚举改成对 B 每一位的枚举，然后计算 |j-x|=b_k 的两个解 x_1 和 x_2，再进行状态转移。易得：

x_1=b_k+j x_2=j-b_k dp_{i,j}=\min_{k=1}^m \Bigg \{ \begin{cases} x_1\geq 0,dp_{i-1,x_1} \\ x_2\geq 0,dp_{i-1,x_2} \end{cases} +[j<a_i]\Bigg \}

这样做的时间复杂度为 O(nmN)，或者可以理解为 O(m\sum a_i)，可以通过此题。

代码

#include <bits/stdc++.h>
using namespace std;
#define il inline
const int N = 510, M = 1e3 + 10;
int dp[N][M], a[N], b[N], n, m;
bool vis[M];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;++i)
        scanf("%d", &a[i]);
    for(int i = 1;i <= m;++i)
        scanf("%d", &b[i]);
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0;i <= a[1];++i)
        dp[1][i] = (i < a[1]);
    for(int i = 2;i <= n;++i)
    {
        for(int j = 0;j <= a[i];++j)
        {
            for(int k = 1;k <= m;++k)
            {
                int x1 = b[k] + j, x2 = j - b[k];
                if(x1 >= 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][x1] + (j < a[i]));
                if(x2 >= 0)
                    dp[i][j] = min(dp[i][j], dp[i - 1][x2] + (j < a[i]));
            }
        }
    }
    int ans = dp[0][0];
    for(int i = 0;i <= a[n];++i)
        ans = min(ans, dp[n][i]);
    if(ans < dp[0][0]) // 特判无解
        cout << ans;
    else
        cout << -1;
    return 0;
}