自动搬运

查看原文

来自洛谷，原作者为

	A7F3jK9pR0xf_ DFS = Dead Fat Sheep |百万罚时过大江

搬运于2025-08-24 23:13:33，当前版本为作者最后更新于2025-05-11 16:10:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门

思路

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

我们发现 $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;
}