USACO 2.3.4 Money Systems 解题报告

题目大意很简单，就是给出钱币系统，求能拼出V的情况总数

可以用DP求解，注意到 money [ j ] [ i ] += money [ j - k * sys [ i - 1 ] ] [ i - 1 ] ;

其中money [ j ] [ i ] 表示用前i种币拼出j的情况总数，明显题目要求的是money [ n ] [ v ]

usaco 2.3.4 Money Systemsview raw

/* 
ID:shiryuw1 
PROG:money 
LANG:C++ 
*/ 
#include<iostream> 
#include<cstdlib> 
#include<cstdio> 
#include<cstring> 
#include<algorithm> 
#include<cmath> 
using namespace std; 
int sys [ 30 ] ; 
long long money [ 10005 ] [ 30 ] = { 0 } ; 
int main() 
{ 
    freopen("money.in","r",stdin); 
    freopen("money.out","w",stdout); 
    int v , n ; 
    cin >> v >> n ; 
    int i , j , k ; 
    for ( i = 0 ; i < v ; i ++ ) 
    { 
        cin >> sys [ i ] ; 
    } 
    sort ( sys , sys + v );

    for ( i = 0 ; i <= n ; i ++ ) 
    { 
        if ( i % sys [ 0 ] == 0 ) 
            money [ i ] [ 1 ] = 1; 
        else 
            money [ i ] [ 1 ] = 0 ; 
    } 
    for ( i = 2 ; i <= v ; i ++ ) 
    { 
        for ( j = 0 ; j <= n ; j ++ ) 
        { 
            for ( k = 0 ; j >= k * sys [ i - 1 ] ; k ++ ) 
            { 
                money [ j ] [ i ] += money [ j - k * sys [ i - 1 ] ] [ i - 1 ] ; 
            } 
        } 
    }

    printf ( "%lld\n" , money [ n ] [ v ] ); 
    return 0; 
}