有三種硬幣，每種有自己的幣值。

然后有n次詢問，每次都給出每種硬幣的數(shù)量和要付的錢s，求有多少種付法。n<=1000 s<=100000

------

不考慮限制，就是個簡單dp....

有限制的時候，我們可以考慮反過來用總的方案數(shù)量剪掉不合法的。

根據(jù)容斥原理，不合法的情況=

有1種硬幣數(shù)量不合法即第1種不合法+第2+第3+第4 ?再去掉有兩個不合法的12種都不合法-23種都不合法-34種都不合法-........加上三種不合法的即123種不合法+124不合法... ?最后減去1234都不合法。

所以每次詢問都這樣做一遍，讓一種硬幣不合法只要付比他的限制多一個就可以了，剩下的錢可以隨意付，直接去dp里查值。

復(fù)雜度4*s+n*2^4

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f;
}ll ans;
int c[5],x[5],n,s;
ll f[100005];void dfs(int i,int p,int sum)
{// printf("%d %d %d\n",i,p,sum);if(i>4){ans+=p*f[sum];return;}dfs(i+1,p,sum);if(sum>=c[i]*(x[i]+1))dfs(i+1,-p,sum-c[i]*(x[i]+1));
}int main()
{for(int i=1;i<=4;i++)c[i]=read();f[0]=1;for(int i=1;i<=4;i++)for(int j=c[i];j<=100000;j++)f[j]+=f[j-c[i]];n=read();for(int i=1;i<=n;i++){for(int j=1;j<=4;j++)x[j]=read();s=read();ans=0;dfs(1,1,s);printf("%lld\n",ans);}return 0;
}

?

轉(zhuǎn)載于:https://www.cnblogs.com/FallDream/p/bzoj1042.html

總結(jié)

以上是生活随笔為你收集整理的[bzoj1042][HAOI2008]硬币购物的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。