poj3181 Dollar Dayz (DP+大数)
发布时间：2020-12-13 21:06:11 所属栏目：PHP教程 来源：网络整理
导读：Dollar Dayz Crawling in process... Crawling failed Time Limit: 1000 MS Memory Limit: 65536 KB 64bit IO Format: %I64d %I64u Submit Status Practice POJ 3181 Appoint description: System Crawler (2016-05⑵7) Description Farmer John goes to Dol
|
Dollar Dayz
Crawling in process...
Crawling failed
Time Limit:1000MS
Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Appoint description:
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$1Write 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
其中dp数组存贮组成当前数的个数 import java.math.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sca =new Scanner(System.in);
int k,n;
while(sca.hasNext())
{
n=sca.nextInt();
k=sca.nextInt();
BigInteger dp []=new BigInteger[1005];
for(int i=0;i<1005;i++)
dp[i]=BigInteger.ZERO;
dp[0]=BigInteger.ONE;
for(int i=1;i<=k;i++){
for(int j=0;j<=n;j++){
if(j>=i&&dp[j-i]!=BigInteger.ZERO){
dp[j]=dp[j].add(dp[j-i]);
}
}
}
System.out.println(dp[n]);
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |