复习笔记之母函数

HDU 1398 Square Coins

　　题意：给 17 种面值的钱币，分别为：1-4-9-。。。-17^2.问 x（x <= 300) 能有多少种不同的兑换方式。

　　思考：略~母函数简单模板题目。事实上还可以用完全背包来做。

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <algorithm>
using namespace std ;
const int maxn = 333 ;
int w[20] , c1[maxn] , c2[maxn] , k , N = 17 ;

inline void muhanshu()
{
    for (int i = 0 ; i <= k ; ++ i) c1[i] = 1 , c2[i] = 0 ;
    for (int p = 2 ; p <= N ; ++ p) {
        for (int i = 0 ; i <= k ; ++ i) {
            for (int j = 0 ; j + i <= k ; j += w[p]) {
                c2[j+i] += c1[i] ;
            }
        }
        for (int i = 0 ; i <= k; ++ i) c1[i] = c2[i] , c2[i] = 0 ;
    }
    printf("%d\n",c1[k]) ;
}

int f[maxn] ;

void beibao()
{
    memset(f,0,sizeof(f)) ;
    f[0] = 1 ;
    for (int i = 1 ; i <= N ; ++ i) {
        for (int j = w[i] ; j <= k ; ++ j) {
            f[j] += f[j-w[i]] ;
        }
    }
    printf("%d\n",f[k]) ;
}

int main()
{
    for (int i = 1 ; i <= 17 ; ++ i) w[i] = i*i ;
    while (scanf("%d",&k) == 1 && k) {
        //muhanshu() ;
        beibao() ;
    }
    return 0 ;
}

 HDU 1709 The Balance

题意：有 N 个砝码，一个天平，问 1 到 砝码之和范围内的数字哪个不能组成，注意，砝码放在同一边加，两边减，也就是说每个砝码可以取 -1个，0个，1个。

 　思考：需要思考么？？不过因为幂次可能有负数，所以同乘砝码和就ok了，注意输出格式。

　　

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstring>
#include <queue>
using namespace std ;
const int maxn = 20010 ;
int c1[maxn] , c2[maxn] , sum , N , A[maxn] ;

int main()
{
//    freopen("1.txt","r",stdin) ;
    while (scanf("%d",&N) == 1) {
        sum = 0 ;
        for (int i = 1 ; i <= N ; ++ i) scanf("%d",&A[i]) , sum += A[i] ;
        memset(c1,0,sizeof(c1)) ;
        memset(c2,0,sizeof(c2)) ;
        c1[0] = c1[A[1]] = c1[2*A[1]] = 1 ;
        for (int k = 2 ; k <= N ; ++ k) {
            for (int i = 0 ; i <= sum*2 ; ++ i) {
                for (int j = 0 ; j <= 2  && (i+j*A[k] <= sum*2) ; ++ j)
                c2[i+j*A[k]] += c1[i] ;
            }
            for (int i = 0 ;i <= sum*2 ; ++ i) c1[i] = c2[i] , c2[i] = 0 ;
        }
        int ans[10010] , cnt = 0 ;
        for (int i = sum + 1 ; i <= sum*2 ; ++ i) if (c1[i] == 0) ans[++cnt] = i - sum ;
        printf("%d\n",cnt);
        for (int i = 1 ; i <= cnt ; ++ i) {
            if (i == cnt) printf("%d\n",ans[i]);
            else printf("%d ",ans[i]);
        }
    }
    return 0 ;
}

~end~