link

服了，竟然没看出来限制条件是高度。

dp 参考状态 dp[i][prev_h]

• i: 当前位置
• prev_h: 上一个甘蔗的高度
• 记录的是最小砍刀次数

dp 参考状态转移 dp[i][prev_h] 的值来源于 dp[i][prev_h ± b]

dp 参考代码 使用了滚动数组进行优化

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXH = 1000;

int main()
{
  int n, m;
  cin >> n >> m;

  vector<int> A(n);
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }

  vector<int> B(m);
  for (int i = 0; i < m; i++) {
    cin >> B[i];
  }
  sort(B.begin(), B.end());
  //不用去重，题目说了是集合了
  //B.erase(unique(B.begin(), B.end()), B.end())

  //状态是高度。因为求最小，所以初始最大化
  //在这里，状态压缩了，只表示上一个甘蔗不同高度的次数
  vector<int> dp(MAXH + 1, INF);

  //状态是从上一个位置的不同高度转移过来的
  //所以填表遍历顺序就是 位置 -> 高度
  //那么初始化就要先初始化第一根甘蔗的所有高度，
  //不然下一个位置转移不了

  for (int h = 0; h <= A[0]; ++h) {
    dp[h] = (h == A[0] ? 0 : 1);
    //不等于原来的高度说明砍了，初始化为1
  }

  for (int i = 1; i < n; i++) {
    vector<int> next_dp(MAXH + 1, INF);

    for (int h = 0; h <= A[i]; ++h) {
      int min_prev = INF;
      for (int b: B) {
        if (h - b >= 0) 
          min_prev = min(min_prev, dp[h-b]);
        if (h + b <= MAXH)
          min_prev = min(min_prev, dp[h+b]);
      }
      next_dp[h] = min_prev + (h == A[i] ? 0 : 1);
    }
    dp = next_dp;
  }

  int result = INF;
  for (int h = 0; h <= MAXH; ++h) {
    result = min(dp[h], result);
  }

  if (result >= INF) {
    cout << -1 << "\n";
  } else {
    cout << result << "\n";
  }

  return 0;
}