代码

//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;

namespace mine
{
	typedef long long ll;
	const int INF=0x3f3f3f3f;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(int num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void writeln(int num){write(num);puts("");}
	#define pr pair<int,int>
	#define FR first
	#define SE second
	#define MP make_pair
	inline void chmin(ll &x,ll y) {x=x<y?x:y;}

	const int MAX_N=31,MAX_M=2e5+10;
	int n,m,mn;ll f[2][MAX_N][MAX_M];
	//bool v[MAX_M];
	// void solve(int st,int num,int lst,int t)//环上
	// {
	// 	ll mi=f[lst][t][st]-num;v[st]=1;int tot=1;
	// 	for(int i=2,now=(st+num)%mn;now!=st;now=(now+num)%mn,i++,tot++)
	// 	{
	// 		v[now]=1;
	// 		chmin(f[lst][t][now],(ll)num*i+mi);
	// 		mi=min(mi,-(ll)num*i+f[lst][t][now]);
	// 	}
	// 	for(int i=1,now=st;now!=st or i==1;now=(now+num)%mn,i++) chmin(f[lst][t][now],(ll)num*(tot+i)+mi);
	// }
	stack<int> sta;//int ru[MAX_M];
	void insert(int num)//基环树无限背包
	{
		for(int t=0;t<m;t++)
			for(int now=0;now<mn;now++)
				chmin(f[0][t+1][(now+num)%mn],f[1][t][now]+num);

		for(int lst=0;lst<=1;lst++) for(int t=0;t<=m;t++)
		{
			static int ru[MAX_M];static bool v[MAX_N];
			//memset(v,0,sizeof v);memset(ru,0,sizeof ru);
			for(int now=0;now<mn;now++) ru[(now+num)%mn]++;
			for(int now=0;now<mn;now++) if(ru[now]==0) sta.push(now);
			while(sta.size())
			{
				int x=sta.top();sta.pop();v[x]=1;
				int y=(x+num)%mn;ru[y]--;if(ru[y]==0) sta.push(y);
				chmin(f[lst][t][y],f[lst][t][x]+num);
			}
			for(int st=0;st<mn;st++) if(!v[st])
			{
				ll mi=f[lst][t][st]-num;v[st]=1;int tot=1;
				for(int i=2,now=(st+num)%mn;now!=st;now=(now+num)%mn,i++,tot++)
				{
					v[now]=1;
					chmin(f[lst][t][now],(ll)num*i+mi);
					mi=min(mi,-(ll)num*i+f[lst][t][now]);
				}
				for(int i=1,now=st;now!=st or i==1;now=(now+num)%mn,i++) chmin(f[lst][t][now],(ll)num*(tot+i)+mi);
			}
			// solve(st,num,lst,t);
		}


		// int vis[MAX_M];
		// memset(vis,0,sizeof vis);
		// for(int i=0;i<mn;i++) if(vis[i]^1)
		// {
		// 	int q[MAX_M],r=0;memset(q,0,sizeof q);
		// 	for(int j=i;;)
		// 	{
		// 		q[++r]=j; j=(j+num)%mn;
		// 		vis[j]=1; if(j==i) break;
		// 	}
		// 	for(int j=1;j<=m;j++)
		// 	{
		// 		ll o=2e18; int p;
		// 		for(int k=1;k<=r;k++) if(f[0][j][q[k]]<o) o=f[0][j][q[k]], p=k;
		// 		for(int k=p,b;;k=b)
		// 		{
		// 			b=k%r+1; chmin(f[0][j][q[b]],f[0][j][q[k]]+num);
		// 			if(b==p) break;
		// 		}
		// 	}
		// }
	}
	pr c[MAX_N];map<int,int> tmp;vector<int> coin[MAX_N];
	void main()
	{
		n=qread(),m=0,mn=INF;
		for(int i=1;i<=n;i++)
		{
			c[i].SE=qread();mn=min(mn,c[i].SE);
			int col=qread();if(!tmp.count(col)) tmp[col]=++m;
			c[i].FR=tmp[col];
		}
		sort(c+1,c+n+1);for(int i=1;i<=n;i++) coin[c[i].FR].push_back(c[i].SE);
		bool bk=1;//强行放最后
		for(int i=1;i<=m;i++)
			for(int t=0;t<(int)coin[i].size();t++) if(bk and coin[i][t]==mn)
				{swap(coin[i],coin[m+1]);bk=0;break;}

		memset(f,0x3f,sizeof f);f[1][0][0]=0;
		for(int i=1;i<=m+1;i++)
		{
			for(int j=0;j<i;j++) for(int t=0;t<mn;t++) chmin(f[1][j][t],f[0][j][t]);
			for(int t=0;t<(int)coin[i].size();t++) insert(coin[i][t]);
		}

		int q=qread();
		while(q--)
		{
			ll wt=qread();
			int ans=-1;
			for(int lst=0;lst<=1;lst++) for(int t=0;t<=m;t++)
			{
				ll tmp=f[lst][t][wt%mn];if(tmp>wt) continue;
				if(tmp+mn<=wt) ans=max(ans,t+lst);
				else ans=max(ans,t);
			}
			writeln(ans);
		}
 	}
};
int main()
{
	srand(time(0));
	mine::main();
}

评测结果