HDU-2110-Crisis of HDU（母函数完全背包）

Crisis of HDU

Problem Description

话说上回讲到HDU大战东洋小苟，结果自然是中方大胜，这一战也使得海东集团在全球同行业中的地位更加巩固。随着集团的发展，很多创业时期的元老逐步功成身退，先是8600移民海外，然后是linle夫妇退隐山林，逐渐的，最初众多的元老只剩下XHD夫妇和Wiskey三人了。 到了2020年，因为扩张过度加上老鼠数量逐年减少，公司的发展遇到了前所未有的危机，此时集团已经没有任何流动资金，更可怕的是，这个时候，wiskey也决定退出了！ 退出本身并不麻烦，麻烦的是，退出的人需要取走相应比例（1/3）金额的资产。 假设公司此时一共有n种价值的资产，每种价值的资产数量已知，请帮助心烦意乱的XHD夫妇计算一共有多少种分割资产的方法。

Input

输入包含多个测试实例，每个实例的第一行是一个整数n(n<100)，表示一共有n种价值的资产，接着的n行每行包含两个整数pi和mi(0<pi,mi<10)，分别表示某种价值和对应的数量，n为0的时候结束输入。

Output

对于每个测试实例，请输出分割资产的方案数%10000，如果不能分割，请输出“sorry”，每个实例的输出占一行。

Sample Input

2 1 1 2 1 0

Sample Output

1

解题思路：

也是比较裸的母函数题了。 完全背包自然也能写。

AC代码（母函数）：

#include <cstdio> #include <vector> #include <queue> #include <cstring> #include <cmath> #include <map> #include <set> #include <stack> #include <string> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", n) #define pc(n) printf("%c", n) #define pdd(n,m) printf("%d %d", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sc(n) scanf("%c",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define ss(str) scanf("%s",str) #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) #define mem(a,n) memset(a, n, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mod(x) ((x)%MOD) #define gcd(a,b) __gcd(a,b) #define lowbit(x) (x&-x) #define pii map<int,int> #define mk make_pair #define rtl rt<<1 #define rtr rt<<1|1 #define Max(x,y) (x)>(y)?(x):(y) #define int long long typedef pair<int,int> PII; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int MOD = 1e9 + 7; const ll mod = 10007; const double eps = 1e-9; const ll INF = 0x3f3f3f3f3f3f3f3fll; //const int inf = 0x3f3f3f3f; inline int read(){int ret = 0, sgn = 1;char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')sgn = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){ret = ret*10 + ch - '0';ch = getchar();} return ret*sgn;} inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');} int qpow(int m, int k, int mod){int res=1%mod,t=m%mod;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;} ll gcd(ll a,ll b){if(b > a) swap(a,b); return b==0?a : gcd(b,a%b);} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll inv(ll x,ll mod){return qpow(x,mod-2,mod)%mod;} //const int N = 3e3+15; int t = 1,cas = 1; int n,m; const int N = 5e5+3; int a[N],b[N]; int c1[N],c2[N]; signed main() { while(cin>>n && n) { int sum = 0; for(int i = 0 ; i < n ; i ++){ cin>>a[i]>>b[i]; sum += a[i]*b[i]; } for(int i = 0 ; i <= sum ; i ++){ c1[i] = c2[i] = 0; } for(int i = 0 ; i <= b[0] ; i ++){ c1[i*a[0]] = 1; } int maxx = b[0]*a[0]; for(int i = 1 ; i < n ; i ++) { for(int j = 0 ; j <= maxx ; j ++){ for(int k = 0 ; k <= b[i] ; k ++){ c2[j+k*a[i]] = (c2[j+k*a[i]]+c1[j])%10000; } } maxx += b[i]*a[i]; for(int j = 1; j <= maxx ; j ++){ c1[j] = c2[j]; c2[j] = 0; } } if(sum%3 || c1[sum/3] == 0){ cout<<"sorry"<<endl; } else{ cout<<c1[sum/3]<<endl; } } }

AC代码（完全背包）：

#include <cstdio> #include <vector> #include <queue> #include <cstring> #include <cmath> #include <map> #include <set> #include <stack> #include <string> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d\n", n) #define pc(n) printf("%c", n) #define pdd(n,m) printf("%d %d", n, m) #define pld(n) printf("%lld\n", n) #define pldd(n,m) printf("%lld %lld\n", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sc(n) scanf("%c",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define ss(str) scanf("%s",str) #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,a,n) for(int i=n;i>=a;i--) #define mem(a,n) memset(a, n, sizeof(a)) #define debug(x) cout << #x << ": " << x << endl #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define mod(x) ((x)%MOD) #define gcd(a,b) __gcd(a,b) #define lowbit(x) (x&-x) #define pii map<int,int> #define mk make_pair #define rtl rt<<1 #define rtr rt<<1|1 #define Max(x,y) (x)>(y)?(x):(y) //#define int long long typedef pair<int,int> PII; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int MOD = 1e9 + 7; const ll mod = 10007; const double eps = 1e-9; const ll INF = 0x3f3f3f3f3f3f3f3fll; //const int inf = 0x3f3f3f3f; inline int read(){int ret = 0, sgn = 1;char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')sgn = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){ret = ret*10 + ch - '0';ch = getchar();} return ret*sgn;} inline void Out(int a){if(a>9) Out(a/10);putchar(a%10+'0');} int qpow(int m, int k, int mod){int res=1%mod,t=m%mod;while(k){if(k&1)res=res*t%mod;t=t*t%mod;k>>=1;}return res;} ll gcd(ll a,ll b){if(b > a) swap(a,b); return b==0?a : gcd(b,a%b);} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} ll inv(ll x,ll mod){return qpow(x,mod-2,mod)%mod;} //const int N = 3e3+15; int t = 1,cas = 1; int n,m; const int N = 5e3+3; typedef long long ll; vector<int> G[N]; int cnt[2]; int color[N]; int mark[N]; int a[N],b[N],dp[N]; int tt = 0; int flag = 1; signed main() { while(cin>>n && n) { memset(dp,0,sizeof(dp)); int sum = 0; for(int i = 0 ; i < n ; i ++){ cin>>a[i]>>b[i]; sum += a[i]*b[i]; } dp[0] = 1; for(int i = 0 ; i < n ; i ++){ for(int j = sum; j >= 0; j --){ for(int k = 1; k <= b[i] && a[i]*k <= j; k ++){ dp[j] = (dp[j]+dp[j-a[i]*k])%10000; } } } if(sum%3 || dp[sum/3] == 0){ cout<<"sorry"<<endl; } else{ cout<<dp[sum/3]<<endl; } } }