P1941 | Ficon's Paper

很经典的小游戏。

$dp_{i,j}$ 代表走到 i, j 所需要的最小操作次数。

有几种情况，分类讨论一下：

从上一个位置，进行一次操作
从上一个位置，再进行一次操作（完全背包）
从上一个位置，不进行操作

因为要找最小操作次数，所以数组初始化为 INF

然后第 0 列可以在任意位置开始，所以 $dp_{0, i}=0$

第二种情况不可以从第三种情况进行转移。也就是说，要么一次也不操作，要么操作若干次。

所以需要调换一下转移顺序，先考虑需要操作的情况，再与什么都不做进行比较：

    for (int j = x[i] + 1; j <= m; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j - x[i]] + 1);
      dp[i][j] = min(dp[i][j], dp[i][j - x[i]] + 1);
    }
    for (int j = 1; j <= m - y[i]; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i]]);
    }

但是纵坐标到达 $m$ ，最多只能从 $j-x[i]$ 转移吗？并不是，再往上依旧可以，所以补充：

    for (int j = m - x[i]; j <= m; j++) {
      dp[i][m] = min(dp[i][m], min(dp[i - 1][j], dp[i][j]) + 1);
    }

对于柱子区域最后处理：

    for (int j = 1; j <= m; j++) {
      if (j <= low[i] || j >= high[i]) {
        dp[i][j] = inf;
      }
      minc = min(minc, dp[i][j]);
    }

同时记录一下到达这个横坐标的最小花费，如果无法到达，则退出。

统计一下经过的管子数。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 2e9 + 7;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> x(n + 1), y(n + 1), pipe(n + 1), low(n + 1, 0),
      high(n + 1, m + 1);
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, inf));
  int cnt_pipe = 0;
  for (int i = 1; i <= k; i++) {
    int p, l, h;
    cin >> p >> l >> h;
    low[p] = l, high[p] = h;
    pipe[p] = 1;
  }
  for (int i = 1; i <= m; i++) {
    dp[0][i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    int minc = inf;
    for (int j = x[i] + 1; j <= m; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j - x[i]] + 1);
      dp[i][j] = min(dp[i][j], dp[i][j - x[i]] + 1);
    }
    for (int j = 1; j <= m - y[i]; j++) {
      dp[i][j] = min(dp[i][j], dp[i - 1][j + y[i]]);
    }
    for (int j = m - x[i]; j <= m; j++) {
      dp[i][m] = min(dp[i][m], min(dp[i - 1][j], dp[i][j]) + 1);
    }
    for (int j = 1; j <= m; j++) {
      if (j <= low[i] || j >= high[i]) {
        dp[i][j] = inf;
      }
      minc = min(minc, dp[i][j]);
    }
    if (minc == inf) {
      cout << 0 << endl;
      cout << cnt_pipe << endl;
      return 0;
    }
    if (pipe[i])
      cnt_pipe++;
  }
  int ans = inf;
  for (int i = 1; i <= m; i++)
    ans = min(ans, dp[n][i]);
  cout << 1 << endl;
  cout << ans << endl;
  return 0;
}

我们发现当前状态的转移只跟上一个状态有关，所以进行滚动数组优化：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 2e9 + 7;

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, k;
  cin >> n >> m >> k;
  vector<int> x(n + 1), y(n + 1), pipe(n + 1), low(n + 1, 0),
      high(n + 1, m + 1);
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> y[i];
  }
  vector<vector<int>> dp(2, vector<int>(m + 1, inf));
  int cnt_pipe = 0;
  for (int i = 1; i <= k; i++) {
    int p, l, h;
    cin >> p >> l >> h;
    low[p] = l, high[p] = h;
    pipe[p] = 1;
  }
  for (int i = 1; i <= m; i++) {
    dp[0][i] = 0;
  }
  for (int i = 1; i <= n; i++) {
    int minc = inf;
    for (int j = 1; j <= m; j++) // 记得这里要清理以前的数据
      dp[i & 1][j] = inf;
    for (int j = x[i] + 1; j <= m; j++) {
      dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j - x[i]] + 1);
      dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1][j - x[i]] + 1);
    }
    for (int j = 1; j <= m - y[i]; j++) {
      dp[i & 1][j] = min(dp[i & 1][j], dp[i & 1 ^ 1][j + y[i]]);
    }
    for (int j = m - x[i]; j <= m; j++) {
      dp[i & 1][m] = min(dp[i & 1][m], min(dp[i & 1 ^ 1][j], dp[i & 1][j]) + 1);
    }
    for (int j = 1; j <= m; j++) {
      if (j <= low[i] || j >= high[i]) {
        dp[i & 1][j] = inf;
      }
      minc = min(minc, dp[i & 1][j]);
    }
    if (minc == inf) {
      cout << 0 << endl;
      cout << cnt_pipe << endl;
      return 0;
    }
    if (pipe[i])
      cnt_pipe++;
  }
  int ans = inf;
  for (int i = 1; i <= m; i++)
    ans = min(ans, dp[n & 1][i]);
  cout << 1 << endl;
  cout << ans << endl;
  return 0;
}