DP - 完全背包 - Pay the Price - UVA - 10313
题意：
有n种货币，面值依次是1,2,...,n，现需在一些限制的情况下凑出n元。：有n种货币，面值依次是1,2,...,n，现需在一些限制的情况下凑出n元。：有n种货币，面值依次是1,2,...,n，现需在一些限制的情况下凑出n元。：
①、输入一个整数n，表示求用1,2,...,n凑出n元的方案总数。①、输入一个整数n，表示求用1,2,...,n凑出n元的方案总数。①、输入一个整数n，表示求用1,2,...,n凑出n元的方案总数。
②、输入两个整数n,l，表示求用1,2,...,l凑出n元的方案总数。②、输入两个整数n,l，表示求用1,2,...,l凑出n元的方案总数。②、输入两个整数n,l，表示求用1,2,...,l凑出n元的方案总数。
③、输入三个整数n,l,r，表示求用l,l+1,...,r凑出n元的方案总数。③、输入三个整数n,l,r，表示求用l,l+1,...,r凑出n元的方案总数。③、输入三个整数n,l,r，表示求用l,l+1,...,r凑出n元的方案总数。
其中，任何一种货币数量都是无限的。其中，任何一种货币数量都是无限的。其中，任何一种货币数量都是无限的。
Sample Input：
6
6 3
6 2 5
6 1 6
Sample Output：
11
7
9
11
例如：
对n=6的情况，11种凑法如下：对n=6的情况，11种凑法如下：对n=6的情况，11种凑法如下：
1 1 1 1 1 1
2 2 2
3 3
6
1 1 1 1 2
1 1 2 2
1 1 1 3
1 1 4
1 5
2 4
1 2 3
数据范围：
0<=n<=300Time limit：3000 ms0<=n<=300\\Time \ limit：3000\ ms0<=n<=300Time limit：3000 ms
分析：
将小于等于n正整数ni视作体积为ni的物品，n视作背包容量，问题转化为完全背包求方案总数。将小于等于n正整数n_i视作体积为n_i的物品，n视作背包容量，问题转化为完全背包求方案总数。将小于等于n正整数ni视作体积为ni的物品，n视作背包容量，问题转化为完全背包求方案总数。
状态表示：f[i][j]:考虑小于等于j的数，求和恰好为i的方案总数。状态表示：f[i][j]:考虑小于等于j的数，求和恰好为i的方案总数。状态表示：f[i][j]:考虑小于等于j的数，求和恰好为i的方案总数。
状态计算：①、不包含整数j:f[i][j]=f[i][j−1]。②、包含k个整数j：f[i][j]=f[i][j−1]+f[i−k×j][j−1]，k>=1且i−k×j>=0。状态计算：\\①、不包含整数j:f[i][j]=f[i][j-1]。\\②、包含k个整数j：f[i][j]=f[i][j-1]+f[i-k×j][j-1]，k>=1且i-k×j>=0。状态计算：①、不包含整数j:f[i][j]=f[i][j−1]。②、包含k个整数j：f[i][j]=f[i][j−1]+f[i−k×j][j−1]，k>=1且i−k×j>=0。
完全背包优化，包含整数j时：f[i][j]=f[i][j−1]+f[i−j][j−1]+f[i−2×j][j−1]+...+f[i−k×j][j−1]完全背包优化，包含整数j时：\\f[i][j]=f[i][j-1]+f[i-j][j-1]+f[i-2×j][j-1]+...+f[i-k×j][j-1]完全背包优化，包含整数j时：f[i][j]=f[i][j−1]+f[i−j][j−1]+f[i−2×j][j−1]+...+f[i−k×j][j−1]
f[i][j−i]=f[i−j][j−1]+f[i−2×j][j−1]+...+f[i−k×j][j−1]f[i][j-i]=\qquad \qquad f[i-j][j-1]+f[i-2×j][j-1]+...+f[i-k×j][j-1]f[i][j−i]=f[i−j][j−1]+f[i−2×j][j−1]+...+f[i−k×j][j−1]
于是有f[i][j]=f[i][j−1]+f[i−j][j]。于是有f[i][j]=f[i][j-1]+f[i-j][j]。于是有f[i][j]=f[i][j−1]+f[i−j][j]。
那么容易计算出利用价值在区间[l,r]的货币凑出i元的方案总数为f[i][r]−f[i][l−1]。那么容易计算出利用价值在区间[l,r]的货币凑出i元的方案总数为f[i][r]-f[i][l-1]。那么容易计算出利用价值在区间[l,r]的货币凑出i元的方案总数为f[i][r]−f[i][l−1]。
读入略微麻烦，可以用sscanf函数操作。另需注意l与r不能越界。读入略微麻烦，可以用sscanf函数操作。\\另需注意l与r不能越界。读入略微麻烦，可以用sscanf函数操作。另需注意l与r不能越界。
代码：
#include
#include
#include
#define ll long long
using namespace std;
const int N = 310;
char s[N];
int n,l,r,cnt;
ll f[N][N];
int main()
{
f[0][0] = 1;
for (int i = 0; i <= 300; i++)
for (int j = 1; j = j) f[i][j]+= f[i - j][j];
}
while (gets(s) != NULL)
{
cnt = sscanf(s, "%d %d %d", &n, &l, &r);
l=min(300,l);r=min(300,r);
if (cnt == 1) printf("%lld\n",f[n][n]);
else if (cnt == 2) printf("%lld\n",f[n][l]);
else printf("%lld\n",f[n][r] - f[n][l - 1]);
}
return 0;
}
作者：njuptACMcxk
