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

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

Code

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

很好的一道结合题！