[多謝大佬博客指點(diǎn)迷津]??

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

模板

通用模板——模版一

    //mini為每個(gè)物品最少個(gè)數(shù) ，maxi為每個(gè)物品最多個(gè)數(shù)
    //pi為價(jià)值，m為個(gè)數(shù)     
    int mini[MAX],maxi[MAX],pi[MAX],m[MAX];
    //a為計(jì)算結(jié)果（系數(shù)），b為中間結(jié)果（過程系數(shù)） 
    //a的下標(biāo)表示物品數(shù)，a[]表示對(duì)應(yīng)物品數(shù)下的方案數(shù) 
    int a[MAX],b[MAX];
    //初始化a 
    memset(a,0,sizeof(a));
    a[0]=1;
    //循環(huán)每個(gè)因子，即多少種 
    for(int i=0;i<=n;i++){
        //初始化b 
        memset(b,0,sizeof(b));
        //P為要求的物品價(jià)值（可能的最大指數(shù)）
        //如果問15元由多少種組合，P=15；
        //循環(huán)因子每一項(xiàng) 
        //如果由無限個(gè)，j<=maxi[i]這個(gè)可以省去
        for(int j=mini[i];j<=maxi[i]&&j*pi[i]<=P;j++)
            //循環(huán)a每一項(xiàng) 
            for(int k=0;k+j*pi[i]<=P;k++){
                //把結(jié)果加到對(duì)應(yīng)位 
                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，因?yàn)橛蒪efore，所以這里無需初始化其他位 
    memset(a,0,sizeof(a));
    a[0]=1;
    before=0; 
    for(int i=0;i<=n;i++){
        //計(jì)算下一次 
        _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，現(xiàn)在用的是母函數(shù)，最后輸出的只不過是i而不是系數(shù)，找出系數(shù)為0的最小的i就是最終的結(jié)果

知道個(gè)數(shù)的情況下

方法一：多重背包dp 可以參考一下DP問題這里就懶得貼啦（逃
方法二：母函數(shù)

#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

未知個(gè)數(shù)的情況下

?
方法一：母函數(shù)

#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[]是計(jì)算結(jié)果 
        int i; 
        for(i=before/2;i>=0&&a[i]==0;i--);
        cout<<_next-i<<" "<<i<<endl;
    } 
    return 0;
} 

?

HDU 2079 選課時(shí)間

//#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

個(gè)人建議用第一個(gè)模板

模版一

//#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++){//次數(shù) 
            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];//因?yàn)樘炱接袃蛇?
                }
            }
            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;
}