状压dp+二分

Problem Description

Finally, Little Q gets his weapon at level 10^5105 in the RPG game, now he is trying to beat the boss as soon as possible. The boss has HH units of health point (HP), Little Q needs to cause at least HH units of damage to beat the boss.

Little Q has learnt nn skills, labeled by 1,2,\dots,n1,2,…,n. Each skill can not be used multiple times, because there is not enough time for Little Q to wait for the skill to cool down. Assume Little Q uses the ii-th skill at the xx-th frame, the actor controlled by him will take t_iti​ frames to perform, which means Little Q will not be allowed to use other skills until the (x+t_i)(x+ti​)-th frame. The length of the damage sequence of the ii-th skill is len_ileni​, which means the skill will cause d_{i,j}di,j​ (0\leq j < len_i0≤j

The game starts at the 00-th frame. Your task is to help Little Q beat the boss as soon as possible, or determine Little Q can't beat the boss using all the skills at most once.

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=19,M=1e5+5;
ll f[1<
ll d[N][M];
int t[N],len[N];
int p[1<
int n;ll h;
bool check(int x)
{
	for(int i=0;i<(1<
	{
		int sum=0;
		f[i]=0;
		for(int j=0;j
		{	
			if((i>>j)&1) 
			{
				int now=p[i]-t[j+1];
				if(x-now+1>=1&&x-now+1<=len[j+1])
				f[i]=max(f[i],f[i^(1<1][x-now+1]);
				else if(x-now+1>len[j+1])f[i]=max(f[i],f[i^(1<1][len[j+1]]);
				else f[i]=max(f[i],f[i^(1<
			}
		}
	}
	return (f[(1<-1]>=h);
}
void solve()
{
	scanf("%d%lld",&n,&h);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&t[i],&len[i]);
		for(int j=1;j<=len[i];j++) 
		{
			scanf("%lld",&d[i][j]);
			d[i][j]+=d[i][j-1];
		}
	}
	for(int i=0;i<(1<
	{
		p[i]=0;
		for(int j=0;j
		{
			if((i>>j)&1) p[i]+=t[j+1];
		}
	}
	int l=0,r=2e6;
	int ans=-1;
	while(l<=r)
	{
		int m=(l+r)/2;
		if(check(m))
		{
			ans=m;
			r=m-1;
		}
		else l=m+1;
	}
	printf("%d\n",ans);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}