CCPCx2050 F - 冰水挑战 (DP)

2019-04-14 00:24 +0800

2019-06-06 23:24 +0800

题意

有$n$个挑战,每个挑战如果接受需要消耗$a_i$点体力;但挑战之前体力会变成$\min(x, b_i)$,完成挑战时体力会变为$x - a_i$。无论是否接受第$i$个挑战都可以恢复$c_i$体力。问最多可以接受多少个挑战。

思路

这题既视感很强……因为在问题求解3的时候出(搬运)过一道OJ题(JSOI2007 建筑抢修),该题可以用贪心解决:通过维护一个最大堆记录之前的选择,当前剩余体力不够时撤销之前的某次挑战并改为接受本次挑战来使得当前的选择更优(剩余体力更多)。

但本题接受挑战时体力会变为$\min(x, b_i)$,这是一个非线性的变化,不能通过增加减少的值复原,所以上面的贪心做法就不成立了。

假设前$i$个挑战中接受了$j$个,当前剩余体力的最大值可以表示为$dp[i][j]$,那么状态转移方程可以表示为 $$dp[i][j] = \max \begin{cases} dp[i-1][j] + c_i, \ \min(dp[i-1][j-1], b_i) - a_i + c_i \end{cases}$$

注意第二个转移是有条件的:接受挑战到完成挑战之间体力值必须为正数,特判一下即可。最后用记忆化搜索,寻找最大的$j$使得$dp[n][j] > 0$即为答案。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll n = 0, x = 0;
ll a[1005] = {};
ll b[1005] = {};
ll c[1005] = {};
ll dp[1005][1005] = {};

ll calc(ll i, ll j) {
  if (i < 0 || j < 0 || i < j) return -INF;
  if (i == 0 && j == 0) return x;
  if (dp[i][j] != -1) return dp[i][j];
  else {
    dp[i][j] = calc(i - 1, j) + c[i - 1];
    if (min(calc(i - 1, j - 1), b[i - 1]) > a[i - 1]) {
      dp[i][j] = max(dp[i][j], min(calc(i - 1, j - 1), b[i - 1]) - a[i - 1] + c[i - 1]);
    }
    return dp[i][j];
  }
}

ll solve() {
  ll ans = 0;
  memset(dp, -1, sizeof(dp));
  cin >> n >> x;
  for (ll i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i];
  for (ll i = 0; i <= n; ++i) {
    if (calc(n, i) > 0) ans = i;
  }
  return ans;
}

int main() {
  cin.sync_with_stdio(false);
  cin.tie(NULL);
  cin.exceptions(cin.failbit);

  int T = 0;
  cin >> T;
  for (int i = 0; i < T; ++i) {
    cout << solve() << endl;
  }

  return 0;
}