描述
http://poj.org/problem?id=3181
FJ有n元钱,有k种商品,各为1,2,...,k-1,k元,问有多少种花掉这n元钱的方法.
Dollar Dayz
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5858 | Accepted: 2197 |
Description
Farmer John goes to Dollar Days at The Cow Store and discovers an unlimited number of tools on sale. During his first visit, the tools are selling variously for $1, $2, and $3. Farmer John has exactly $5 to spend. He can buy 5 tools at $1 each or 1 tool at $3 and an additional 1 tool at $2. Of course, there are other combinations for a total of 5 different ways FJ can spend all his money on tools. Here they are:
1 @ US$3 + 1 @ US$2
1 @ US$3 + 2 @ US$1
1 @ US$2 + 3 @ US$1
2 @ US$2 + 1 @ US$1
5 @ US$1
Write a program than will compute the number of ways FJ can spend N dollars (1 <= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).
Input
A single line with two space-separated integers: N and K.
Output
A single line with a single integer that is the number of unique ways FJ can spend his money.
Sample Input
5 3
Sample Output
5
Source
分析
这是一个完全部分和问题.对于多重部分和问题,可以用多重背包,但是由于有三层循环,会超时(即便使用二进制优化),所以有特殊的算法.而完全部分和问题可以直接用完全背包做.
注意:
1.是大数,要用高精度,或者两位分别存高低位:
unsigned long long 上限是1.8e19,所以每一位存1e17.
2.注意如果高位有数,低位要保证有前导0.
#include <cstdio>
#include <algorithm>
#define ull unsigned long long
const int maxw=,maxn=;
const ull mod=;
int W,N;
ull dp[maxw][]; void solve()
{
dp[][]=;
for(int i=;i<=N;i++)
{
for(int j=i;j<=W;j++)
{
dp[j][]+=dp[j-i][];
dp[j][]+=dp[j-i][];
dp[j][]+=dp[j][]/mod;
dp[j][]%=mod;
}
}
if(dp[W][])
{
printf("%llu",dp[W][]);
printf("%017llu\n",dp[W][]);
}
else
{
printf("%llu\n",dp[W][]);
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("john.in","r",stdin);
freopen("john.out","w",stdout);
#endif
scanf("%d%d",&W,&N);
solve();
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
system("john.out");
#endif
return ;
}