母函数

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

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;
}

最后编辑于：2019.07.08 20:54:57

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 199,340评论 5赞 467
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 83,762评论 2赞 376
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 146,329评论 0赞 329
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 53,678评论 1赞 270
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 62,583评论 5赞 359
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 47,995评论 1赞 275
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,493评论 3赞 390
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,145评论 0赞 254
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,293评论 1赞 294
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,250评论 2赞 317
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,267评论 1赞 328
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 32,973评论 3赞 316
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,556评论 3赞 303
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,648评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 30,873评论 1赞 255
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,257评论 2赞 345
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 41,809评论 2赞 339

母函数

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

模板

知道个数的情况下

未知个数的情况下

推荐阅读更多精彩内容