小明的任务清单

#include<algorithm>
#include<map>
using namespace std;
int n,N;
long long int MAX,a[30],t[30];
map<long long int,long long int>ans;
void dfs(int step,long long int ai,long long int ti)
{
	if(step==n)
	{
		ans[ti]=max(ai,ans[ti]);//记录每种组合对应时间和完成的最大数量
		return;
	}
	else
	{	
		dfs(step+1,ai+a[step],ti+t[step]);//不选
		dfs(step+1,ai,ti);//不选
	}
}
int main(void)
{
	//空闲时间很大，dp要开很大会爆空间
	//而n却出奇的少，所以用dfs
	//但是询问次数很多，所以不能根据输入的空闲时间来dfs
	//而是要提前将所有组合可能先算完
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(int i=0;i<n;i++)
		scanf("%d",&t[i]);
	dfs(0,0,0);
	int Size=ans.size(),i=0;
	long long int A[Size],T[Size];
	for(auto it=ans.begin();it!=ans.end();it++)
	{//将a和t对应的map进行最值化处理的同时分出2个数组存，方便之后二分
		if(it->second<MAX)
			it->second=MAX;
		T[i]=it->first,A[i]=it->second;
		//printf("time=%lld a=%lld\n",T[i],A[i]);
		MAX=max(MAX,it->second);
		i++;
	}
	scanf("%d",&N);
	long long int space;
	for(int i=0;i<N;i++)
	{
		scanf("%lld",&space);
		if(space<T[0])
		{
			printf("0\n");
			continue;
		}
		else if(space>=T[Size-1])
		{
			printf("%lld\n",A[Size-1]);
			continue;
		}
		int index=upper_bound(T,T+Size,space)-T-1;
		printf("%lld\n",A[index]);
		//二分找到第一个大于space的再减1就是所求
	}
	return 0;
}