Boss Rush (two-point answer + DP)

Boss Rush

题意
给定 n 个技能,每个技能只能用一次.
Each skill has a cooldown $t_i$,If a skill is in time x 释放,那么直到 $x+t_i-1$ No other skills can be released during this time.
Each skill has a damage duration $le{n}_i$,If the skill is in time x 释放,Then it will be in th $x+j(0\le j<le{n}_i)$ 时刻产生 $d_{i,j}$ 伤害.
问,Set the life value to H 的 boss How long does it take to beat the minimum？
$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,Find the maximum damage dealt.
But the time is not fixed,There is no way to minimize the time spent,So consider the dichotomous answer to fix the time,Then in this time frame the pressureDP,See if the maximum damage dealt is greater than that H.

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

Enumerates all collections from small to large,对于当前集合,Iterate over all events that are not in this collection,Use the state of the collection 更新 Plus the state of the collection after the event：
To maximize damage,Each skill is released at the minimum release time.
The minimum time for the current skill to release is ,The sum of the cooldowns of all skills in the set.Damage starts at the time of release,to release time + len[i] - 1 结束,The end time should be equal to the time of two minutes T 取 min.
f[i | 1 << j] = max(f[i | 1<<j], f[i] + dmg[j][min(end-sum, len[j]-1)]);

The last time was very tight,to prune.
1.When enumerating all collections,If the current collection has not been updated,Then there is no need to update other collections,直接跳过.So initialization initializes all states to -1,0状态初始为0.If the collection state is -1 就跳过.Because the collection it is about to update has already been deleted 0 Status updated.
2.Exit immediately after the current damage is satisfied,There is no need to update all collections.
3.It is also possible to preprocess the sum of the cooling times for each set,This way you don't have to do it every time.

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];  //This block can be preprocessed
		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++) //When using the shape pressure, the array position should be as small as possible0开始 
		{
    
			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;
}

---

A good combination question！