【CodeChef】LECOINS（同余最短路，背包DP）

题意：给定n个物品，每个物品可以取无限次，每个物品有两种属性：价值v和颜色c

现在有q个询问，每次询问是否能取出价值和为S的方案，如有多解输出不同颜色种数的最大值

题意：看到BZOJ评论区有好心人说CC上有上一题的加强版就写了一下

首先按颜色分组，每组中取或不取只有0/1

对于每组内部就是一个同余最短路

设dp[i][j][k]为当前组不取(0)/取(1)，当前共有j种不同的，模意义下和为k的最小总价值

每次建图跑SPFA转移，每次询问时暴力从大到小枚举颜色种数判断是否有解

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef long double ld;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,ll>P;

 #define N  200010

 #define M  6000010

 //#define INF 1e9

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 #define fors(i) for(auto i:e[x]) if(i!=p)

 const int MOD=1e8+,inv2=(MOD+)/;

       int p=1e4+;

       double eps=1e-;

       int dx[]={-,,,};

       int dy[]={,,-,};

 struct arr

 {

     int x,y;

 }a[N];

 bool cmp(arr a,arr b)

 {

     return a.y<b.y;

 }

 struct node

 {

     int x,y,z;

     node(){}

     node(int a,int b,int c){x=a,y=b,z=c;}

 }q[];

 ll dis[][][N],INF;

 int vis[][][N],mn,c;

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 ll readll()

 {

    ll v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void spfa(int now)

 {

     int t=,w=;

     q[]=node(,,);

     vis[][][]=;

     rep(i,,)

      rep(j,,c)

       rep(k,,mn-)

        if(dis[i][j][k]!=INF)

        {

            w++;

            q[w]=node(i,j,k);

            vis[i][j][k]=;

        }

     while(t<w)

     {

         t++;

         int x=q[t].x,y=q[t].y,z=q[t].z;

         vis[x][y][z]=;

         int A=,B=y+-x,C=(z+now)%mn;

         if(dis[x][y][z]+now<dis[A][B][C])

         {

             dis[A][B][C]=dis[x][y][z]+now;

             if(!vis[A][B][C])

             {

                 w++;

                 q[w]=node(A,B,C);

                 vis[A][B][C]=;

             }

         }

     }

 }

 int main()

 {

     //freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

     int n=read();

     mn=1e9;

     rep(i,,n) a[i].x=read(),a[i].y=read(),mn=min(mn,a[i].x);

     sort(a+,a+n+,cmp);

     mem(dis,0x3f);

     INF=dis[][][];

     c=;

     dis[][][]=;

     rep(i,,n-)

     {

         if(a[i].y!=a[i+].y)

         {

             rep(j,,c)

              rep(k,,mn-) dis[][j][k]=min(dis[][j][k],dis[][j][k]);

         }

         spfa(a[i+].x);

         if(a[i].y!=a[i+].y) c++;

     }

     rep(j,,c)

      rep(k,,mn-) dis[][j][k]=min(dis[][j][k],dis[][j][k]);

     int Q=read();

     while(Q--)

     {

         ll x=readll();

         int u=x%mn;

         int flag=;

         per(i,n,)

         {

             if(dis[][i][u]<=x)

             {

                 printf("%d\n",i);

                 flag=;

                 break;

             }

         }

          if(!flag) printf("-1\n");

     }

     return ;

 }