10313 - Pay the Price
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=1254
In ancient days there was a country whose people had very interesting habits. Some of them were lazy, some were very rich, some were very poor and some were miser. Obviously, some of the rich were miser (A poor was never miser as he had little to spend) and lazy but the poor were lazy as well (As the poor were lazy they remained poor forever). The following things were true for that country
a) As the rich were miser, no things price was more than300 dollars (Yes! their currency was dollar).
b) As all people were lazy, the price of everything was integer (There were no cents and so beggars always earned at least one dollar)
c) The values of the coins were from1 to 300 dollars, so that the rich (who were idle) could pay any price with a single coin.
Your job is to find out in how many ways one could pay a certain price using a limited number of coins (Note that the number of coins paid is limited but not the value or source. I mean there was infinite number of coins of all values). For example, by using three coins one can pay six dollars in 3 ways, 1+1+4, 1+2+3, and 2+2+2. Similarly, one can pay6 dollars using 6 coins or less in 11 ways.
Input
The input file contains several lines of input. Each line of input may contain1, 2 or 3 integers. The first integer is alwaysN (0<=N<=300), the dollar amount to be paid. All other integers are less than1001 and non-negative.
Output
For each line of input you should output a single integer.
When there is only one integer N as input, you should output in how many waysN dollars can be paid.
When there are two integers N andL1 as input, then you should output in how many ways N dollars can be paid usingL1 or less coins.
When there are three integers N,L1 and L2 as input, then you should output in how many waysN dollars can be paid using L1, L1+1 …,L2 coins (summing all together). Remember that L1 is not greater thanL2.
Sample Input
6
6 3
6 2 5
6 1 6
Sample Output
11
7
9
11
思路：
这个题目涉及到一个结论，用不超过j个硬币凑出面值i的方案种数，是和用面值不超过j的硬币凑出面值i的方案种数是相同的。说得再数学一点，就是整数i拆分成不超过j个整数的拆分数，是和整数i拆成若干个值不超过j的整数的拆分数是相同的。具体的证明用到了Ferrers图像的性质。
这样的话我们就可以取一个二维数组f[i][j]表示用面值不超过j的硬币凑出面值i的方案的种数，那么如果我使用了面值j，对应方案种数就应该加上f[i-j][j]，如果我们不使用面值j，那么对应的方案种数就应该加上f[i][j-1]。也就是说状态转移方程为f[i][j]= f[i-j][j]+ f[i][j-1]。
完整代码：
/*0.055s*/
#include<bits/stdc++.h>
using namespace std;
const int maxn = 301;
char s[20];
long long dp[maxn][maxn];
int main()
{
int n, L1, L2;
dp[0][0] = 1;
for (int i = 0; i < maxn; ++i)
{
for (int j = 1; j < maxn; ++j)
{
if (j <= i) dp[i][j] = dp[i - j][j] + dp[i][j - 1];
else dp[i][j] = dp[i][j - 1];
}
}
while (gets(s))
{
L1 = L2 = -1;
sscanf(s, "%d%d%d", &n, &L1, &L2);
L1 = min(L1, 300), L2 = min(L2, 300);
if (L1 == -1) printf("%lld\n", dp[n][n]);
else if (L2 == -1) printf("%lld\n", dp[n][L1]);
else
{
if (L1 < 2) printf("%lld\n", dp[n][L2]);
else printf("%lld\n", dp[n][L2] - dp[n][L1 - 1]);
}
}
return 0;
}
查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索was
， lazy
， of
， The
c整数拆分
10313轴承、10313 徐州医学院、pay the bill、pay the ghost、pay to the order of，以便于您获取更多的相关知识。