USACO Training Section 2.3 Money Systems
程序员文章站
2022-06-07 19:41:53
...
[url="http://ace.delos.com/usacoprob2?a=4iVBI4338BO&S=money"]英文原题[/url] [url="http://www.wzoi.org/usaco/12%5C207.asp"]中文题译[/url]
大意：给定钞票面值，问给定的钱数有多少种付钱方式。
设有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，完全没问题。不过，注意到这个递归方程中只用到上一层的数据，因而用一维数组就可以搞定了。
大意：给定钞票面值，问给定的钱数有多少种付钱方式。
设有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;
}