题目链接：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;
}