（2022杭电多校三）1002-Boss Rush（状压DP+二分）

题目链接：ssss - Virtual Judge

 

样例输入：

3
1 100
5 3
50 60 70
2 100
2 3
40 40 100
100 2
20 5
1 1000
1 1
999

样例输出：

1
2
-1

题意：多组样例，每组样例先给一个n和H，分别代表技能数和boss血量，接下来对于每个技能都有两行输入，第一行给出两个数分别代表技能使用时间t[i]和技能持续时间len[i]，接下来一行给出len[i]个数，分别代表每一秒可以对Boss造成的伤害，我们使用一个技能后，在使用该技能期间会对Boss造成伤害，但是无法使用其他技能，问我们杀死Boss所需要的最小时间，如果无法杀死Boss就直接输出-1.

分析：看了一下数据范围，发现技能最多只有18个，然后就想到了用状压去做，我们可以二分时间，设置二分边界分别为0，1e18，那么二分复杂度就是log(1e18)，f[st]表示技能使用状态为st的条件下在某段时间内最多造成的伤害（某段时间是二分值），这个更新过程是n*2^n，所以总的复杂度就是O（log(1e18)*n*2^n）。

下面来看一下如何进行动态转移。

我们要判断是否能在T时间内打败Boss，那么我们的f[st]就表示技能使用状态为st的条件下在时间T内对Boss最多造成的伤害值，我们需要从1~（1<<n）枚举技能使用状态st，我们需要预处理一下到达任意状态所需要的时间，假如当前状态是st，如果当前状态的伤害值大于Boss血量H，那么我们就直接返回true，如果当前状态所需要的时间大于T，那么我们就没必要继续更新当前状态的下一个状态了，因为利用当前状态去更新的下一个状态所使用的技能会更多，花费时间也会更多，没有意义。我们更新状态是枚举当前状态下还没有使用的技能，比如是技能i，如果使用第i个技能后总时间依旧没有到达T，那么我们就把当前技能的伤害值全部计入f[st|(1<<i)]，如果要是使用第i个技能后总时间超过了T，那么由于我们的技能伤害从开始使用时就已经开始计算，所以我们只需要计算在T时间前的这一段时间所造成的伤害即可。注意我们利用的是技能使用状态达到st所需要的时间，也就是说技能释放的时间和而不是技能持续时间和，一定要搞清楚两者之间的关系，按照这个更新过程去更新答案，如果更新到最后也没有一个状态st使得f[st]>=H，那么就返回false.

下面是代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll sum[20][N];//sum[i][j]表示第i个技能前j秒可以造成的伤害 
ll H,n,t[20],len[20];
ll f[1<<20];//f[st]表示状态st在某段时间内最多造成的伤害（某段时间是二分值）
ll sumt[1<<20];//sumt[st]表示触发技能在状态st下最少需要的触发时间
bool check(ll T)
{
	ll ans=0;
	for(int i=1;i<1<<n;i++) f[i]=-1;
	f[0]=0;
	for(int st=0;st<1<<n;st++)
	{
		ll w=f[st]; 
		if(w==-1) continue;//说明当前状态st在t时间内无法完全触发
		if(w>=H) return true;//说明状态st下在t时间内造成的伤害已经可以杀死怪物 
		if(sumt[st]>T) continue;
		for(int i=0;i<n;i++)//枚举还未触发的技能 
		{
			if(st>>i&1) continue;//该技能已触发
			if(sumt[st]+len[i]-1<=T) 
				f[st|(1<<i)]=max(f[st|(1<<i)],f[st]+sum[i][len[i]]);
			else	
				f[st|(1<<i)]=max(f[st|(1<<i)],f[st]+sum[i][T-sumt[st]+1]);
		}
	}
	return false;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		scanf("%lld%lld",&n,&H);
		for(int i=0;i<n;i++)
		{
			scanf("%lld%lld",&t[i],&len[i]);
			for(int j=1;j<=len[i];j++)
			{
				scanf("%lld",&sum[i][j]);
				sum[i][j]+=sum[i][j-1];
			}
		}
		for(int st=1;st<1<<n;st++)//预处理触发技能在状态st下最少需要的触发时间
		{
			sumt[st]=0;//别忘了初始化 
			for(int i=0;i<n;i++)
			if(st>>i&1) sumt[st]+=t[i];
		}
		ll l=0,r=1e18;
		while(l<r)
		{
			ll mid=l+r>>1;
			if(check(mid)) r=mid;
			else l=mid+1;
		}
		if(check(l)) printf("%lld\n",l);
		else puts("-1");
	}
	return 0;
}