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

题目描述

小蓝种了一排甘蔗，甘蔗共 $n$ 根，第 $i$ 根甘蔗的高度为 $a_i$。小蓝想砍一些甘蔗下来品尝，但是他有强迫症，不希望甘蔗的高度显得乱糟糟的。具体来说，他给出了一个大小为 $m$ 的整数集合 B={b1,b2,⋯ ,bm}B = \{b_1, b_2, \cdots, b_m\}B={b1​,b2​,⋯,bm​}，他希望在砍完甘蔗后，任意两根相邻的甘蔗之间的高度差 $|a_i-a_{i+1}|$ 都要在这个集合 $B$ 中。小蓝想知道他最少需要砍多少根甘蔗（对于高度为 $h$ 的甘蔗，他可以将其砍成 $x$ 高度的甘蔗，x∈{0,1,2,⋯ ,h−1}x \in \{0, 1, 2, \cdots, h-1\}x∈{0,1,2,⋯,h−1}）。

输入格式

输入的第一行包含两个正整数 $n,m$，用一个空格分隔。

第二行包含 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$，相邻整数之间使用一个空格分隔。

第三行包含 $m$ 个正整数 $b_1,b_2,\cdots ,b_m$，相邻整数之间使用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不能满足条件，输出 $-1$。

输入输出样例 #1

输入 #1

6 3
6 7 3 4 9 12
2 3 5

输出 #1

2

输入输出样例 #2

输入 #2

2 1
4 5
6

输出 #2

-1

说明/提示

样例说明 1

其中一种方案：将 $a_2$ 砍为 $3$，再将 $a_3$ 砍为 $1$。

评测用例规模与约定

• 对于 $40\%$ 的评测用例，$1\le n,m\le 8$；
• 对于所有评测用例，$1\le n,m\le 500$，$1\le a_i\le 1000$，$0\le b_i\le 1000$。

C++实现

#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;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容