题目链接:Problem - 7163 (hdu.edu.cn)
题意 / Problem
有一个人要打Boss,他有n个技能且每个技能最多释放一次,怪物有H血量,问这个人打败Boss最短时间,如果不能打败输出-1。
思路 / Thought
因为要求最短时间,如果给定一个时间可以用较小的复杂度O(2 ^ n)算出这个时间是否可以打败Boss,所以考虑用二分。找到分界点就找到了答案,因为题目要求的是打败怪兽的第一帧,所以最后的答案要减一。
如何来判断呢?因为N比较小,容易想到用状压dp,将技能从0 ~ n - 1编号,技能状态st的不同位表示不同技能的启用状态,1用,0不用。技能转移过程是每次从已有的技能状态转移到“多用一个技能”的状态,就是找一个为0的二进制位并改成1算出时间和伤害是否满足要求。
其中dp数组表示的是“技能组st”打出的最大伤害,在每次转移之前需要判断这个技能能不能打出来,再判断能不能打完。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e5 + 10; int t[20], len[20], N, H, sumt[1 << 19], sum[20][maxn], dp[1 << 19]; bool check(int T)//判断T能否打败boss { memset(dp, 0, sizeof(int) * (1 << N)); for(int st = 0;st < (1 << N); ++ st) { if(dp[st] >= H)return true; if(sumt[st] >= T)continue;//已经超时不能在用技能了 //再加一个技能 for(int i = 0;i < N; ++ i) { if(st & (1 << i))continue;//已经用了的不能用 //只要还有一帧就能用新技能 int new_st = st | (1 << i);//新的状态 if(sumt[st] + len[i] <= T)//技能i的伤害能打满 dp[new_st] = max(dp[new_st], dp[st] + sum[i][len[i]]); else dp[new_st] = max(dp[new_st], dp[st] + sum[i][T - sumt[st]]); } } return false; } void solve() { cin >> N >> H; for(int i = 0;i < N; ++ i)//技能从0到N - 1编号,方便构造技能组 { cin >> t[i] >> len[i]; for(int j = 1;j <= len[i]; ++ j) { int x;cin >> x; sum[i][j] = sum[i][j - 1] + x;//单个技能i的伤害前缀和 } } for(int st = 0;st < (1 << N); ++ st)//st表示技能组 { sumt[st] = 0; for(int i = 0;i < N; ++ i)//计算释放完某技能组所需的时间 if(st & (1 << i))sumt[st] += t[i]; } int l = 0, r = 1e18; while(l + 1 != r) { int mid = (l + r) >> 1; if(check(mid))r = mid; else l = mid; } cout << (check(r) ? r - 1 : -1) << '\n'; } signed main() { ios::sync_with_stdio(0); int _;cin >> _; while(_ --)solve(); return 0; }
Comments NOTHING