# CCPCx2050 F - 冰水挑战 (DP)

2019-04-14 00:24 +0800

2019-06-06 23:24 +0800

## 代码

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


Comments are disabled due to technical issues.
Alternative: mail to blog.doowzs[at]outlook.com