(2022 Hangdian multi school III) 1002 boss rush (pressure dp+ dichotomy)

Topic link ：ssss - Virtual Judge

 

The sample input ：

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

Sample output ：

1
2
-1

The question ： Multiple sets of samples , Each group of samples is given one n and H, Represent the number of skills and boss Blood volume , Next, there are two lines of input for each skill , The first line gives two numbers, representing the skill use time t[i] And skill duration len[i], The next line shows len[i] Number , Each second can be represented by Boss Damage done , After we use a skill , During the use of this skill, you will Boss Cause harm , But you can't use other skills , Ask us to kill Boss Minimum time required , If you can't kill Boss Output directly -1.

analysis ： Take a look at the data range , At most, there are only 18 individual , Then I thought of using shape pressing , We can have two minutes , Set the bisection boundaries as 0,1e18, Then the binary complexity is log(1e18),f[st] Indicates that the skill use status is st The maximum damage caused in a certain period of time under the condition of （ A certain period of time is a binary ）, The update process is n*2^n, So the overall complexity is O（log(1e18)*n*2^n）.

Let's take a look at how to perform dynamic transfer .

We have to decide whether we can T Defeat in time Boss, So our f[st] It means that the skill use status is st Under the condition of time T Internal pair Boss The maximum damage caused , We need to go from 1~（1<<n） Enumerate skill usage status st, We need to preprocess the time required to reach any state , If the current state is st, If the damage value of the current state is greater than Boss Blood volume H, Then we'll go straight back true, If the current state takes longer than T, Then we don't need to continue to update the next state of the current state , Because using the current state to update the next state will use more skills , It will take more time , It makes no sense . We update the status to enumerate the skills that have not been used in the current status , For example, skills i, If section i The total time still hasn't arrived after skills T, Then we will take all the damage value of the current skill into account f[st|(1<<i)], If you use the i The total time after skills exceeds T, Since our skill damage has been calculated since the beginning of use , So we just need to calculate in T The damage caused by this period of time before time can be . Note that we use skills to achieve st The time required , That is to say, the sum of skill release time is not the sum of skill duration , We must make clear the relationship between the two , Follow this update process to update the answer , If it is updated to the end, there is no status st bring f[st]>=H, So return false.

Here is the code ：

#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] It means the first one i Before skills j The damage that seconds can cause  
ll H,n,t[20],len[20];
ll f[1<<20];//f[st] According to state st The most damage caused in a certain period of time （ A certain period of time is a binary ）
ll sumt[1<<20];//sumt[st] Indicates that the trigger skill is in the state st The minimum trigger time required 
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;// State the current state st stay t It cannot be triggered completely in time 
		if(w>=H) return true;// Description status st Next in t The damage caused in time can already kill the monster  
		if(sumt[st]>T) continue;
		for(int i=0;i<n;i++)// Enumerate skills that have not been triggered  
		{
			if(st>>i&1) continue;// This skill has been triggered 
			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++)// Preprocessing trigger skill in status st The minimum trigger time required 
		{
			sumt[st]=0;// Don't forget to initialize  
			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;
}