USACO Training Section 2.3 Money Systems

英文原题  中文题译

大意：给定钞票面值，问给定的钱数有多少种付钱方式。

设有m种钞票，每种面值为v[i](0<=i<m)，钱数为n的付钱方式为s[n]，则s[n]=sum_{0<=i<m}{s[n-v[i]]}。这是最简单直接了当的想法。但不对：这样会导致重复计数。重新考虑，事实上我们是在找方程sum_{0<=i<m}{x[i]*v[i]}=n的解的数目，应该对i做规划。显然有sum_{0<=i<m-1}{x[i]*v[i]}=n-x[m-1]*v[m-1]。令DP[j][s]=|{x[i]| sum_{0<=i<j}{x[i]*v[i]}=s}|即用前j种钞票付钱s的方式的数量，则有DP[j][s]=sum_{0<=k*v[j]<=s}DP[j-1][s-v[j]*k]，而DP[m][n]即为我们要的解。注意初始值：DP[0][s]=[s%v[0]==0]，这里s=0时s[i][0]=1。看一下数据限制：1<=n<=10,000, 1<=m<=25，完全没问题。不过，注意到这个递归方程中只用到上一层的数据，因而用一维数组就可以搞定了。

/*
ID: blackco3
TASK: money
LANG: C++
*/
#include <iostream>
#include <memory.h>
using namespace std;
#define _max_num_ 10000
#define _max_type_ 25
long long _DP[_max_type_][_max_num_+1], _val[_max_type_];
int _type, _num ;

int main() {
	freopen("money.in", "r", stdin);
	freopen("money.out", "w", stdout);	
	cin >> _type >> _num ;
	for( int i=0; i<_type; i++ )
		cin >> _val[i] ;
	memset( _DP, 0, sizeof(_DP) );
	for( int i=0; i<=_num; i+=_val[0] )
		_DP[0][i]=1 ;
	for( int i_type=1; i_type<_type; i_type++ )
		for( int i_num=0; i_num<=_num; i_num++ )
			for( int i_used=0; i_used<=i_num; i_used+=_val[i_type] )
				_DP[i_type][i_num] += _DP[i_type-1][i_num-i_used] ;
	cout << _DP[_type-1][_num] << endl ;		
	return 0;
}