母函数

[多谢大佬博客指点迷津]👇

https://blog.csdn.net/CHN_JZ/article/details/73065465
https://blog.csdn.net/xiaofei_it/article/details/17042651

---

模板

通用模板——模版一

    //mini为每个物品最少个数 ，maxi为每个物品最多个数
    //pi为价值，m为个数     
    int mini[MAX],maxi[MAX],pi[MAX],m[MAX];
    //a为计算结果（系数），b为中间结果（过程系数） 
    //a的下标表示物品数，a[]表示对应物品数下的方案数 
    int a[MAX],b[MAX];
    //初始化a 
    memset(a,0,sizeof(a));
    a[0]=1;
    //循环每个因子，即多少种 
    for(int i=0;i<=n;i++){
        //初始化b 
        memset(b,0,sizeof(b));
        //P为要求的物品价值（可能的最大指数）
        //如果问15元由多少种组合，P=15；
        //循环因子每一项 
        //如果由无限个，j<=maxi[i]这个可以省去
        for(int j=mini[i];j<=maxi[i]&&j*pi[i]<=P;j++)
            //循环a每一项 
            for(int k=0;k+j*pi[i]<=P;k++){
                //把结果加到对应位 
                b[k+j*pi[i]]+=a[k];
            }
        //把b值赋给a 
        memcpy(a,b,sizeof(b));   
    }

提高效率——模板二

int mini[MAX],maxi[MAX],pi[MAX],m[MAX];
    int a[MAX],b[MAX],before,_next;
    //初始化a，因为由before，所以这里无需初始化其他位 
    memset(a,0,sizeof(a));
    a[0]=1;
    before=0; 
    for(int i=0;i<=n;i++){
        //计算下一次 
        _next=min(before+pi[i]*m[i],P);
        //只清空b[0.._next] 
        memset(b,0,sizeof(int)*(_next+1));
        for(int j=mini[i];j<=maxi[i]&&j*pi[i]<=_next;j++)
            for(int k=0;k+j*pi[i]<=_next;k++){
                b[k+j*pi[i]]+=a[k];
            }
        //把b从0到_next的值赋给a 
        memcpy(a,b,sizeof(int)*(_next+1)));  
        before=_next;
    }

---

 

HDU 1085 Holding Bin-Laden Captive!

想搞掂一下这道题，之前用的dp，现在用的是母函数，最后输出的只不过是i而不是系数，找出系数为0的最小的i就是最终的结果

知道个数的情况下

方法一：多重背包dp 可以参考一下DP问题这里就懒得贴啦（逃
方法二：母函数

#include <bits/stdc++.h>
using namespace std;
int m[3],a[10000],b[10000],before,_next;
int pi[3]={1,2,5};

int main(){
    while(cin>>m[0]>>m[1]>>m[2]&&(m[0]!=0||m[1]!=0||m[2]!=0)){
        a[0]=1;
        before=0;
        for(int i=0;i<=2;i++){
            _next=before+m[i]*pi[i];
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i];j++)
                for(int k=0;k<=before;k++)
                    b[k+j*pi[i]]+=a[k];
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        }
        int i;
        for(i=0;i<=_next;i++)
            if(a[i]==0)
                break;
        cout<<i<<endl;
    }
    return 0;
} 

 

Square Coins

未知个数的情况下

 
方法一：母函数

#include <bits/stdc++.h>
using namespace std;
int m[3],a[10000],b[10000],before,_next;
int pi[18],n;

int main(){
    for(int i=1;i<=17;i++)
        pi[i]=i*i;
    while(cin>>n&&n!=0){
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=17;i++){
            memset(b,0,sizeof(b));
            for(int j=0;j*pi[i]<=n;j++)
                for(int k=0;k+j*pi[i]<=n;k++)
                    b[k+j*pi[i]]+=a[k];
            memcpy(a,b,sizeof(b));
        }
        cout<<a[n]<<endl;
    }
    return 0;
} 

 
方法二：背包

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[305],res[305],n;

int main(){
    dp[0]=res[0]=1;
    for(int i=1;i<=17;i++){
        for(int j=0;j+i*i<=300;j++){
            if(dp[j]){
                dp[j+i*i]=dp[j];
                res[j+i*i]+=res[j];
            }
        }
    }
    while(cin>>n&&n)
        cout<<res[n]<<endl;
    return 0;
} 

 

HDU 2110 Crisis of HDU

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[101],m[101],a[10000],b[10100];

int main(){
    while(cin>>n&&n){
        memset(pi,0,sizeof(pi));
        memset(m,0,sizeof(m));
        int sum=0;
        for(int i=0;i<n;i++){
            cin>>pi[i]>>m[i];
            sum+=pi[i]*m[i];
        }
        if(sum%3){
            cout<<"sorry"<<endl;
            continue;
        }
        sum/=3;
        memset(a,0,sizeof(a));
        a[0]=1;
        int before=0;
        int _next;
        for(int i=0;i<n;i++){
            _next=min(before+pi[i]*m[i],sum);
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i]&&j*pi[i]<=_next;j++){
                for(int k=0;k<=before&&k+j*pi[i]<=_next;k++){
                    b[k+j*pi[i]]+=a[k];
                    b[k+j*pi[i]]%=10000;
                }
            }
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        } 
        if(a[sum]>0)
            cout<<a[sum]<<endl;
        else
            cout<<"sorry"<<endl;
    }
    return 0;
} 

 

Big Event in HDU

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[50],m[50],a[250010],b[250010];

int main(){
    while(cin>>n&&n>=0){
        for(int i=0;i<n;i++)
            cin>>pi[i]>>m[i];
        memset(a,0,sizeof(a));
        a[0]=1;
        int before=0;
        int _next; 
        for(int i=0;i<n;i++){
            _next=before+pi[i]*m[i];
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i];j++){
                for(int k=0;k<=_next;k++)
                    b[k+j*pi[i]]+=a[k];
            }
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        }
        //a[]是计算结果 
        int i; 
        for(i=before/2;i>=0&&a[i]==0;i--);
        cout<<_next-i<<" "<<i<<endl;
    } 
    return 0;
} 

 

HDU 2079 选课时间

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[50],m[50],a[2500],b[2500],x[11],y[11];

int main(){
    int t,k;
//  freopen("data","r",stdin);
    cin>>t;
    while(t--){
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        cin>>n>>k;
        for(int i=0;i<k;i++){
            cin>>pi[i]>>m[i];
        }
        int _next;
        int before=0;
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=0;i<k;i++){
            _next=before+pi[i]*m[i];
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i]&&j*pi[i]<=_next;j++){
                for(int p=0;p+j*pi[i]<=_next;p++){
                    b[p+j*pi[i]]+=a[p];
                }
            }
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        }
        cout<<a[n]<<endl;
    }
    return 0;
} 

 

HDU 2082 找单词

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[50],m[50],a[999999],b[999999];

int main(){
    int t,k;
    freopen("data","r",stdin);
    cin>>t;
    for(int i=1;i<=26;i++)
        pi[i]=i;
    while(t--){
        for(int i=1;i<=26;i++)
            cin>>m[i];
        int before=0;
        int _next;
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=26;i++){
            _next=before+pi[i]*m[i];
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=0;j<=m[i]&&j*pi[i]<=_next;j++)
                for(int k=0;k+pi[i]*j<=_next;k++)
                    b[k+j*pi[i]]+=a[k];
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        }
        int sum=0;
        for(int i=0;i<=50;i++){
            sum+=a[i];
        }
        cout<<sum-1<<endl;
    }
    return 0;
} 

 

HDU 2152 Fruit

个人建议用第一个模板

模版一

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[50],m,a[999999],b[999999],mini[101],maxi[101];

int main(){
    int t,k;
//  freopen("data","r",stdin);
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            cin>>mini[i]>>maxi[i];
        }
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=0;i<n;i++){
            memset(b,0,sizeof(b));
            for(int j=mini[i];j<=maxi[i]&&j<=m;j++){
                for(int k=0;k+j<=m&&k<=m;k++)
                    b[k+j]+=a[k];
            }
            memcpy(a,b,sizeof(b));
        }
        cout<<a[m]<<endl;
    }
    return 0;
} 

模板二

//#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,pi[50],m,a[999999],b[999999],mini[101],maxi[101];

int main(){
    int t,k;
    freopen("data","r",stdin);
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            cin>>mini[i]>>maxi[i];
        }
        int before=0;
        int _next; 
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=0;i<n;i++){
            _next=min(before+maxi[i],m);
            memset(b,0,sizeof(int)*(_next+1));
            for(int j=mini[i];j<=_next&&j<=maxi[i];j++){
                for(int k=0;k+j<=_next&&k<=before;k++)
                    b[k+j]+=a[k];
            }
            memcpy(a,b,sizeof(int)*(_next+1));
            before=_next;
        }
        if(before>=m)
            cout<<a[m]<<endl;
        else 
            cout<<0<<endl;
    }
    return 0;
} 

 

HDU 5616 Jam's balance

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
//#include <bits/stdc++.h>
#define maxi 2110 
#define INF 99999999
using namespace std;
int a[maxi],b[maxi],v[maxi];

int main(){
    int t,n,m,c;
    cin>>t;
    while(t--){
        int sum=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        memset(v,0,sizeof(v));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>v[i];
            sum+=v[i];
        }
        a[v[1]]=a[0]=1;//初始化
        for(int i=2;i<=n;i++){//次数 
            memset(b,0,sizeof(b));
            for(int j=0;j<=sum;j++){
                for(int k=0;k+j<=sum&&k<=v[i];k+=v[i]){
                    b[k+j]+=a[j];
                    b[abs(k-j)]+=a[j];//因为天平有两边 
                }
            }
            memcpy(a,b,sizeof(b));
        } 
        cin>>m;
        for(int i=0;i<m;i++){
            cin>>c;
            if(a[c])
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
    }
    return 0;
}