Boss Rush (二分答案 + 状压DP)

Boss Rush

题意
给定 n 个技能，每个技能只能用一次。
每个技能有冷却时间 $t_i$，如果一个技能在时间 x 释放，那么直到 $x+t_i-1$ 时间内就不能再释放其他技能。
每个技能有伤害持续时间 $le{n}_i$，如果技能在时间 x 释放，那么将会在第 $x+j(0\le j<le{n}_i)$ 时刻产生 $d_{i,j}$ 伤害。
问，将生命值为 H 的 boss 击败最少需要用多少时间？
$1\le n\le 18,1\le H\le 10^{18},$
$1\le t_i,le{n}_i\le 100000,1\le d_{i,j}\le 10^9$

思路
n 很小，考虑状压DP，求打出的最大伤害。
但是时间并不固定，无法使得时间花费最少，所以考虑二分答案将时间固定，然后在这个时间范围内状压DP，看打出的最大伤害是否大于 H。

时间复杂度：$O(n\ast 2^n\ast logans)$

从小到大枚举所有集合，对于当前集合，遍历所有不在该集合的事件，用该集合的状态 更新 加上该事件后集合的状态：
为了使得伤害最大，每个技能都在最小能释放的时间释放。
当前技能释放的最小时间为，集合中所有技能的冷却时间之和。伤害从释放的时间开始，到释放时间 + len[i] - 1 结束，结束时间要和二分的时间 T 取 min。
f[i | 1 << j] = max(f[i | 1<<j], f[i] + dmg[j][min(end-sum, len[j]-1)]);

最后时间卡的很紧，要剪剪枝。
1.枚举所有集合的时候，如果当前集合都没有被更新过，那就不用再去更新其他集合了，直接跳过。所以初始化将所有状态初始为-1，0状态初始为0。如果集合状态为 -1 就跳过。因为其要更新的集合已经被 0 状态更新过了。
2.当前伤害满足后立刻退出，没必要更新完所有集合了。
3.也可以把每个集合的冷却时间总和预处理出，这样就不用每次循环求了。

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int t[20], len[20];
int dmg[20][N];
int f[1<<18];

bool check(int mid)
{
    
	int end = mid;
	mem(f, -1);
	f[0] = 0;
	
	for(int i=0;i<1<<n;i++)
	{
    
		if(f[i] == -1) continue;
		
		int sum = 0;
		for(int j=0;j<n;j++) if(i >> j & 1) sum += t[j];  //可以将此块预处理
		if(sum > end) continue;
		
		for(int j=0;j<n;j++)
		{
    
			if(i >> j & 1) continue;
			f[i | 1 << j] = max(f[i | 1<<j], f[i] + dmg[j][min(end-sum, len[j]-1)]);
			if(f[i | 1<<j] >= m) return 1;
		}
	}
	return 0;
}

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n >> m;
		
		int l = 0, r = 0;
		for(int i=0;i<n;i++) //用到状压时数组位置尽量从0开始 
		{
    
			cin >> t[i] >> len[i];
			for(int j=0;j<len[i];j++)
			{
    
				cin >> dmg[i][j];
				if(j) dmg[i][j] += dmg[i][j-1];
			}
			r += t[i] + len[i] - 1; //最大时间
		}
		
		while(l < r)
		{
    
			int mid = l + r >> 1;
			if(check(mid)) r = mid;
			else l = mid + 1;
		}
		if(check(l)) cout << l << endl;
		else cout << -1 << endl;
	}
	
	return 0;
}

---

很好的一道结合题！