題解 找錢

題目描述

做法與心路歷程

好吧這是一道套路題，但不知道套路我太菜了

很明顯的背包，但有個數限制。

一開始寫便想起了1年以前，剛學OI時學dp時看到的一句話:二進制分組。然后就想了$3h$還沒過。

接著又想起了$n$天前學容斥時教練講的$2^n$容斥。特么有O(n)當初還只講了($2^n$)的

好吧考試沒想出來。被A穿了

正確做法

開始套路。

設$f_i$表示小$L$湊出面值為$i$的方案數，$g_i$表示店員湊出面值為$i$的方案數。由于求的方法差不多，所以只看$f$

首先不考慮個數的限制，做一遍完全背包跑出$f_i$,此時$f_i$會有多的貢獻即$a$選了$b+1$個及以上的個數。

考慮將多的貢獻減去，方法為做一遍$01$背包，轉移為$f_i?=f_{i?a(b+1)}$

注意減去要在做完完全背包后立馬進行$01$背包。

最后統計答案用$f_i\times g_{i?X}$即可

$\mathcal{C}ode$

/******************************* Author:galaxy yr LANG:C++ Created Time:2019年10月21日 星期一 14時45分58秒 *******************************/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring>struct IO{template<typename T>IO & operator>>(T&res){T q=1;char ch;while((ch=getchar())<'0' or ch>'9')if(ch=='-')q=-q;res=(ch^48);while((ch=getchar())>='0' and ch<='9') res=(res<<1)+(res<<3)+(ch^48);res*=q;return *this;} }cin;const int maxn=2005; const int mod=1e9+7; int n,X,a[maxn],b[maxn],c[maxn],f[maxn*20],g[maxn*20],ans;int main() {//freopen("deal.in","r",stdin);//freopen("deal.out","w",stdout);cin>>n>>X;f[0]=g[0]=1;for(int i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];b[i]=(b[i]+1)*a[i];c[i]=(c[i]+1)*a[i];}f[0]=1;for(int i=n;i>=1;i--){for(int j=a[i];j<=X+a[i]-1;j++) f[j]=(f[j]+f[j-a[i]])%mod;for(int j=X+a[i]-1;j>=b[i];j--) f[j]=(f[j]-f[j-b[i]]+mod)%mod;for(int j=a[i];j<=2*X;j++) g[j]=(g[j]+g[j-a[i]])%mod;for(int j=2*X;j>=c[i];j--) g[j]=(g[j]-g[j-c[i]]+mod)%mod;}for(int i=X;i<=2*X;i++)ans=(ans+1ll*f[i]*g[i-X]%mod)%mod;printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的题解 找钱的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。