1002 - Boss Rush
每组样例有 $n$ 个技能,每个技能持续时间为 $len_i$,从释放技能的当前秒开始计算,每秒的伤害 $d_{i, j}$ 不同,并且你释放一个技能后有一个冷却时间,在这个时间里你不能放技能,(技能伤害可以叠加), 现在有一个有 $H$ 血的怪兽,试问最短在多少时间能杀死他。$1\le n\le 18, 1\leq H\leq 10^{18}$
由于 $n$ 很小,所以可以枚举放了哪些技能。如果考虑
$$
dp(状态):= 放这些技能杀死怪物最短需要多少时间
$$
是没法转移的,因为技能和技能之前是独立的。
我们可以二分答案,二分一个最短时间。枚举在这个时间内我能造成的最大伤害,如果 $\ge H$,就是答案。
$$
dp(state):=在规定时间内,造成的最大伤害
$$
转移时考虑没放过的技能 $j$,然后计算一下技能 $j$ 能释放多少秒,以及他造成的伤害,这些都可以预处理出来。
$$
dp(state) + damage(j, time_j) \rightarrow 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$ 个邮件,每个邮件在 $l_i$ 天到达邮局,在 $r_i$ 时刻被回收,也就是说这个邮件必须要在 $[l_i,r_i]$ 被拿回去。
你需要把这 $n$ 个邮件全部拿回家中,每一趟可以最多拿走 $k$ 件,问至少需要几趟?
容易想到的是,要最少的趟数,那每个邮件都拖到最后时刻再拿是最好的,因为这样可以顺便拿走最多的邮件。也就是将区间按照右端点递增排序。
假设我们这一趟取的是 $i$ 邮件。那么他前面的 $k - 1$ 个满足 $l_j \leq r_i$ 的邮件我们可以顺带拿走。
所以我们需要枚举前面没有被拿走的邮件的左端点 $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$ 位的数 $s_i$,有两种情况:
- 之前没有出现过。那这次就枚举从 $p$ 取还是从 $q$ 取,然后判断合不合法。
- 如果从 $p$ 中取:我们可以判断出此时已经取了前 $pos_p[s_i] - 1$ 个 $p$ 排列,前 $i - len_p - 1$ 个 $q$ 排列。
- 然后枚举上一位是从 $p$ 还是从 $q$ 取的。很自然的转移到 $dp(i - 1, 0)或者dp(i - 1, 1)$
- 之前出现过。那么此前一定取了 $q$,判一下当前 $p$ 的位置是不是比 $pos_q[s_i]$ 靠前。
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;
}