UVA Pay the Price(10313)

题目大意：

       有0~300这300种价值的金额。 现在可能给出参数：

        1个：n,        输出可以组成价值n的方式的个数。

        2个：n, a，    输出用个数小于a个硬币的组成价值n的方式的个数。

        3个：n, a, b， 输出用个数大于a和小于b个硬币组成价值n的方式的个数。

 

解题大意：

    参考了其他人的说明才知道需要用到Ferrers图像的一个结论进行解题，该结论为：用不超过j个硬币凑出面值i的方案种数，是和用面值不超过j的硬币凑出面值i的方案种数是相同的。

    所以本题就可以认为是用面值不超过j的硬币凑出面值i的方案中数。设dp[i][j]表示用不超过面值j的硬币凑出面值i的方案种数，那么状态转移方程为：

     若i>j，则dp[i][j] += dp[i-j][j];  表示若硬币面值小于i，则用价值为j的硬币凑成i的数量等于自身的数量加上用价值为j的硬币凑成i-j的数量，此外若j-1>0，dp[i][j] += dp[i][j-1];   即还要再加上用价值为j-1的硬币凑成i的数量。

代码如下：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;

#define LOOP(X,Y) for( int X = 0; X < Y; X++ )
#define LOOPP(X, Y, Z) for( int X = Y; X < Z; X++ )
#define SLOOP(X,Y) for( int X = Y; X >= 0; X-- )
#define SLOOPP(X, Y, Z) for( int X = Y; X >= Z; X-- )
#define OPENFILE(PATH) ifstream fin; fin.open(PATH);
#define APENDFILE(PATH) char * file = PATH; ofstream fout( file, ios::out | ios::app );
#define PB push_back
#define ULL unsigned long long
#define LL long long

int coins[301];
LL dp[301][301];

int main()
{
	OPENFILE("test.txt");

	string line;
	int temp;
	vector<int> v;

	memset( dp, 0, sizeof( dp ) );
	dp[0][0] = 1;

        //先算出所有可能，即预处理一下。
	for( int i = 0; i <= 300; i++ )
	{
		for( int j = 1; j <= 300; j++ )   //j不能从0开始，因为硬币的价值至少为1，若从0开始，最后结果会翻一倍。
		{
			if( i - j >= 0 )
				dp[i][j] += dp[i-j][j];
			if( j - 1 >= 0 )
				dp[i][j] += dp[i][j-1]; 
		}
	}

	while(getline( fin, line ))
	{		
		istringstream is(line);
		while( is>>temp )
		{
			v.PB(temp);
		}
		
		if( v.size() == 1 )
			cout<<dp[v[0]][v[0]]<<endl;
		else if( v.size() == 2 )
			cout<<dp[v[0]][v[1]]<<endl;
		else
			cout<<dp[v[0]][v[2]]-dp[v[0]][v[1]-1]<<endl;

		v.clear();
	}
	return 0;
}