洛谷P4241 采摘毒瘤

完了我连背包都不会了……

考虑暴力，先枚举最小的数是哪个，设大小为$d_i$，个数为$k_i$，所有比它小的数的总和是$sum$，然后把所有比它小的全都装进背包，它以及比他大的做一个多重背包，那么设$dp[j]$表示在剩下的这些数里取的总和为$j$时的方案数，那么$$ans+=\sum_{j=m-sum-d_i+1}^{m-sum} dp[j]$$

上面的式子意思就是，将所有比它小的全放进去之后，枚举背包剩余的空间，统计所有方案数。因为不能让把任何大于等于它的在统计之前就放进去，所以下界是$m-sum-d_i+1$

然后现在的问题就是怎么统计了才能过。我们可以从大到小枚举，这样的话每做到一个物品就只需要对它自己做多重背包，不需要重新dp了

接下来的操作真的是学到了……在做多重背包的时候把$j$按照模$d_i$的取值分为不同的组，然后时间复杂度就能优化到$O(nm)$

简单来讲的话，就是转移的时候$dp[j]+=dp[j-d_i]+dp[j-d_i*2]...+dp[j-d_i*k_i]$，发现每一个$j$只会被与它模$d_i$同余的转移到，于是我们枚举这一个余数，统计与它同余的数的前缀和，然后从小到大转移并不断维护前缀和即可（真的很妙）

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,M=1e5+,mod=;

 struct node{

     int k,d;

     inline bool operator <(const node &b)const{return d<b.d;}

 }a[N];

 int n,m,ans,tot,dp[][M],t;

 inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}

 inline int del(int x,int y){return x-y<?x-y+mod:x-y;}

 void ins(int k,int w){

     int sum,H;

     for(int d=;d<=w-;++d){

         H=sum=;

         for(int j=;j<=(m-d)/w;++j){

             sum=add(sum,dp[t^][j*w+d]);

             if(H<j-k) sum=del(sum,dp[t^][(H++)*w+d]);

             dp[t][j*w+d]=sum;

         }

     }

 }

 int main(){

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

     n=read(),m=read();

     for(int i=;i<=n;++i) a[i].k=read(),a[i].d=read(),tot+=a[i].k*a[i].d;

     if(tot<=m) return puts(""),;

     sort(a+,a++n);

     dp[][]=;

     for(int i=n;i;--i){

         tot-=a[i].k*a[i].d,t^=;

         ins(a[i].k-,a[i].d);

         for(int j=max(m-tot-a[i].d+,);j<=m-tot;++j) ans=add(ans,dp[t][j]);

         ins(a[i].k,a[i].d);

     }

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

     return ;

 }

巴特西

洛谷P4241 采摘毒瘤

最新文章

热门文章