題目鏈接

Boss Rush

題目大意

給了我們一個(gè)Boss的血量，然后給了我們$n$個(gè)技能，每個(gè)技能有施法時(shí)間和一個(gè)施法過(guò)程時(shí)間，會(huì)造成一個(gè)持續(xù)性傷害，題目問(wèn)我們最快什么時(shí)候能干掉Boss?

題解

考慮二分答案，然后我們需要進(jìn)行判定在$mid$時(shí)間時(shí)，所能造成的最大傷害是多少，如果大于等于Boss的血量，那么返回true，否則返回false。我們計(jì)算最大傷害時(shí)，可以考慮使用狀壓DP，$f[i]$中的$i$表示一個(gè)狀態(tài)——哪一位為1就代表使用過(guò)哪些技能。具體狀態(tài)轉(zhuǎn)移可以看代碼

代碼

#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; #define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); #define x first #define y second #define int long long #define endl '\n' const int inf = 1e9 + 10; const int maxn = 100010, M = 2000010; const int mod = 1e9 + 7; typedef pair<int,int> PII; typedef long long LL; typedef unsigned long long ULL; typedef long double LD; int n, H; int d[20][maxn], s[20][maxn]; int t[20], len[20]; int f[maxn * 3]; bool check(int mid) {memset(f, -1, sizeof f);f[0] = 0;for(int i = 0; i < 1 << n; i ++){int time = 0;for(int j = 0; j < n; j ++){if(i >> j & 1) time += t[j];}if(time > mid) continue;for(int j = 0; j < n; j ++){if(i >> j & 1) continue;f[i | 1 << j] = max(f[i | 1 << j], f[i] + s[j][min(len[j], mid - time)]);if(f[i | 1 << j] >= H) return true;}}return false; } signed main() {IOS;int T; cin >> T;while(T --){cin >> n >> H;int l = 0, r = 0;for(int i = 0; i < n; i ++){cin >> t[i] >> len[i];r += max(t[i], len[i]);for(int j = 1; j <= len[i]; j ++) cin >> d[i][j];for(int j = 1; j <= len[i]; j ++) s[i][j] = s[i][j - 1] + d[i][j];}while(l < r){int mid = l + r >> 1;if(check(mid)) r = mid;else l = mid + 1;}if(!check(l)) cout << -1 << endl;else cout << l - 1 << endl;} return 0; }

總結(jié)

以上是生活随笔為你收集整理的2022杭电多校 第三场 B题 Boss Rush的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。