1002 - Boss Rush
每组样例有 n 个技能,每个技能持续时间为 leni,从释放技能的当前秒开始计算,每秒的伤害 di,j 不同,并且你释放一个技能后有一个冷却时间,在这个时间里你不能放技能,(技能伤害可以叠加), 现在有一个有 H 血的怪兽,试问最短在多少时间能杀死他。1≤n≤18,1≤H≤1018
由于 n 很小,所以可以枚举放了哪些技能。如果考虑
dp(状态):=放这些技能杀死怪物最短需要多少时间
是没法转移的,因为技能和技能之前是独立的。
我们可以二分答案,二分一个最短时间。枚举在这个时间内我能造成的最大伤害,如果 ≥H,就是答案。
dp(state):=在规定时间内,造成的最大伤害
转移时考虑没放过的技能 j,然后计算一下技能 j 能释放多少秒,以及他造成的伤害,这些都可以预处理出来。
dp(state)+damage(j,timej)→dp(state|(1<<j))
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 5;
int t[20];
int len[20];
long long damage[20][mxN];
long long dp[1 << 18];
long long cd[1 << 18];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
long long h, mx = 0;
cin >> n >> h;
memset(damage, 0, sizeof damage);
memset(cd, 0, sizeof cd);
// vector<int> t(n);
// vector<int> len(n);
// vector<array<long long, mxN>> damage(18);
for (int i = 0; i < n; i++) {
cin >> t[i] >> len[i];
mx += max(t[i], len[i]);
for (int j = 1; j <= len[i]; j++) {
cin >> damage[i][j];
damage[i][j] += damage[i][j - 1];
}
}
// vector<long long> cd(1 << 18);
for (int mask = 1; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (mask >> i & 1) {
cd[mask] = cd[mask ^ (1 << i)] + t[i];
break;
}
}
}
long long l = 0, r = mx;
long long ans = mx;
auto Check = [&](int mid) {
// vector<long long> dp(1 << 18);
memset(dp, 0, sizeof dp);
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] >= h) {
return true;
}
for (int j = 0; j < n; j++) {
if ((mask >> j & 1) == 0) {
int last = max(0ll, mid - cd[mask] + 1);
dp[mask | (1 << j)] = max(dp[mask | (1 << j)], dp[mask] + damage[j][min(len[j], last)]);
if (dp[mask | (1 << j)] >= h) {
return true;
}
}
}
}
return false;
};
while (l <= r) {
long long mid = (l + r) >> 1;
if (Check(mid)) {
ans = min(ans, mid);
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == mx) {
ans = -1;
}
cout << ans << '\n';
}
return 0;
}
1009 - Package Delivery
有 n 个邮件,每个邮件在 li 天到达邮局,在 ri 时刻被回收,也就是说这个邮件必须要在 [li,ri] 被拿回去。
你需要把这 n 个邮件全部拿回家中,每一趟可以最多拿走 k 件,问至少需要几趟?
容易想到的是,要最少的趟数,那每个邮件都拖到最后时刻再拿是最好的,因为这样可以顺便拿走最多的邮件。也就是将区间按照右端点递增排序。
假设我们这一趟取的是 i 邮件。那么他前面的 k−1 个满足 lj≤ri 的邮件我们可以顺带拿走。
所以我们需要枚举前面没有被拿走的邮件的左端点 l,但这是 O(n) 的。考虑用一个 multiset
优化这个过程,维护当前已经拿走的邮件的右端点,以及我顺带拿走了多少个邮件。
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector<pair<int, int>> segs(n);
for (int i = 0; i < n; i++) {
cin >> segs[i].first >> segs[i].second;
}
sort(segs, segs + n, [&](pair<int, int> &a, pair<int, int> &b) {
if (a.second != b.second) {
return a.second < b.second;
}
return a.first < b.first;
});
multiset<pair<int, int>> st;
int ans = 0;
for (int i = 0; i < n; i++) {
int l = segs[i].first, r = segs[i].second;
auto it = st.lower_bound({l, -1});
if (it == st.end()) {
ans++;
if (k > 1) {
st.insert({r, 1});
}
continue;
}
if (it->second + 1 < k) {
st.insert({it->first, it->second + 1});
}
st.erase(it);
}
cout << ans << '\n';
}
return 0;
}
1012 - Two Permutations
给定两个排列 p 和 q,每次你都可以从 p 和 q 的头取一个元素,插到末尾,最后组成长度为2n 的序列 s,试问有多少种方案能组成 s。
每个数只会出现两次,先把不合法的情况判掉。
考虑
dp(i,0):=第i位从p中取的方案数dp(i,1):=第i位从q中取的方案数
对于第 i 位的数 si,有两种情况:
- 之前没有出现过。那这次就枚举从 p 取还是从 q 取,然后判断合不合法。
- 如果从 p 中取:我们可以判断出此时已经取了前 posp[si]−1 个 p 排列,前 i−lenp−1 个 q 排列。
- 然后枚举上一位是从 p 还是从 q 取的。很自然的转移到 dp(i−1,0)或者dp(i−1,1)
- 之前出现过。那么此前一定取了 q,判一下当前 p 的位置是不是比 posq[si] 靠前。
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> p(n + 1), posp(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
posp[p[i]] = i;
}
vector<int> q(n + 1), posq(n + 1);
for (int i = 1; i <= n; i++) {
cin >> q[i];
posq[q[i]] = i;
}
vector<int> s(2 * n + 1);
for (int i = 1; i <= 2 * n; i++) {
cin >> s[i];
}
if (q[1] != s[1] && p[1] != s[1]) {
cout << "0\n";
continue;
}
vector<array<Mint, 2>> dp(2 * n + 1);
dp[0][0] = (p[1] == s[1]);
dp[0][1] = (q[1] == s[1]);
for (int i = 1; i <= 2 * n; i++) {
int x = s[i], y = s[i - 1];
if (posp[x] == posp[y] + 1) {
dp[i][0] += dp[i - 1][0];
}
if (posp[x] == i - posq[y]) {
dp[i][0] += dp[i - 1][1];
}
if (posq[x] == posq[y] + 1) {
dp[i][1] += dp[i - 1][1];
}
if (posq[x] == i - posp[y]) {
dp[i][1] += dp[i - 1][0];
}
}
cout << (dp[n + n][0] + dp[n + n][1]) << '\n';
}
return 0;
}