母函數題目小結

轉載請注明出處，謝謝http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

遇到一個問題，學習一下母函數。

這些題目用DP，遞推都可以解決。

http://acm.hut.edu.cn/?p=277這裡有篇講解不錯。

生成函數主要為兩種，普通型以及指數型。

普通型的一般求解就是模拟多項式系數求解。

而指數型一般數量級很大，需要通過級數化簡。比較坑，要有不錯的高數功底。

HDU 1085Holding Bin-Laden Captive!

http://acm.hdu.edu.cn/showproblem.php?pid=1085

有币值1，2，5的硬币若幹，問你最少的不能組成的币值為多少。

(1+x+x^2+x^3……x^c1)*(1+x^2+x^4……x^2*c2)*(1+x^5+x^10……x^5*c3)

接下來就是求出每項的系數。模拟一下就行了，兩項兩項

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL  long long
#define MOD 29
#define eps 1e-6
#define N 100010
#define zero(a)  fabs(a)<eps
using namespace std;
int val[3]={1,2,5},cnt[3];
int c1[10005],c2[10005];
int main(){
    while(scanf("%d%d%d",&cnt[0],&cnt[1],&cnt[2])!=EOF&&cnt[0]+cnt[1]+cnt[2]){
        int mmax=0;
        for(int i=0;i<3;i++)
            mmax+=cnt[i]*val[i];
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(int i=0;i<=cnt[0];i++)
            c1[i]=1;
        for(int i=1;i<3;i++){
            for(int j=0;j<=mmax;j++)
                for(int k=0;k<=val[i]*cnt[i];k+=val[i])
                    if(j+k<=mmax&&c1[j])
                         c2[j+k]=c1[j];
            for(int j=0;j<=mmax;j++){
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        int i;
        for(i=0;i<=mmax+1;i++)
            if(c1[i]==0)
                break;
        printf("%d\n",i);
    }
    return 0;
}
           

HDU 2079選課時間(題目已修改,注意讀題)

http://acm.hdu.edu.cn/showproblem.php?pid=2079

同樣 是每種物品有一點的價值和一點的數量。

HDU 1171Big Event in HDU

http://acm.hdu.edu.cn/showproblem.php?pid=1171

背包問題，同樣是物品價值和數量。構造普通生成函數

HDU 1028Ignatius and the Princess III

http://acm.hdu.edu.cn/showproblem.php?pid=1028

整數劃分問題，相當于有1，2，3……價值的物品無數。然後便是一樣的構造

HDU 1398Square Coins

http://acm.hdu.edu.cn/showproblem.php?pid=1398

有物品價值1，4，9，16……平方數的物品無數。

HDU 2082 找單詞

http://acm.hdu.edu.cn/showproblem.php?pid=2082

像這類題目，直接要把上限掐斷。提高效率

HDU 2069Coin Change

http://acm.hdu.edu.cn/showproblem.php?pid=2069

找硬币問題，有個限制條件，就是總數不能超過100。可以有很多解法，可以将母函數變形，加一維表示數量

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL  long long
#define MOD 29
#define eps 1e-6
#define N 100010
#define zero(a)  fabs(a)<eps
using namespace std;
int val[5]={1,5,10,25,50};
int c1[255][105]={0},c2[255][105]={0};
int cnt[30];
int main(){
    for(int i=0;i<=100;i++)
        c1[i][i]=1;
    for(int i=1;i<5;i++){
        for(int j=0;j<=250;j++)
            for(int k=0;k+j<=250;k+=val[i])
                for(int r=0;r+k/val[i]<=100;r++)
                    c2[j+k][r+k/val[i]]+=c1[j][r];
        for(int j=0;j<=250;j++)
            for(int k=0;k<=100;k++){
                c1[j][k]=c2[j][k];
                c2[j][k]=0;
            }
    }
    int n;
    while(scanf("%d",&n)!=EOF){
        int ans=0;
        for(int i=0;i<=100;i++)
            ans+=c1[n][i];
        printf("%d\n",ans);
    }
    return 0;
}
           

HDU 1709 The Balance      

杠杆問題，也就是因為有左右之分，價值有正負。為了避免下标出現負的，統一加上某個值，可以是價值總數。      

HDU 2065 "紅色病毒"問題      

http://acm.hdu.edu.cn/showproblem.php?pid=2065      

POJ 3734 Blocks      

這兩題是指數型母函數，需要用到泰勒級數等數學知識。      

詳見這裡http://blog.csdn.net/acm_cxlove/article/details/7831009