poj 3181 Dollar Dayz 钱币兑换问题大数/高精度完全背包

发布时间：2020-12-14 02:10:54 所属栏目：大数据来源：网络整理

导读：Dollar Dayz Time Limit: ?1000MS ? Memory Limit: ?65536K Total Submissions: ?5289 ? Accepted: ?2006 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

Dollar Dayz

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?5289	?	Accepted:?2006

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

Source

USACO 2006 January Silver

竟然必须用高精度，如何能看出来呢？

import java.math.*;
import java.util.Scanner;
public class Main 
{
	static Scanner cin=new Scanner(System.in);
	static int V,n;
	static final int maxn= 100+5;
	static final int maxV= 1000+20;
	
	static BigInteger [] dp=new BigInteger [maxV];
	static int [] cost     =new int [maxn    ];
	
	static void pre()
	{
		for(int i=1;i<=100;i++)
		{
			cost[i]=i;
		}
	}
	public static void main(String args[])
	{
		pre();
		while(cin.hasNextInt()   )
		{
			V=cin.nextInt();
			n=cin.nextInt();
			for(int i=1;i<=V;i++) dp[i]=BigInteger.ZERO;
			dp[0]=BigInteger.ONE;
			for(int i=1;i<=n;i++)
			{
				for(int v=cost[i];v<=V;v++)
				{
					dp[v]=dp[v].add(dp[v-cost[i] ]);
				}
			}
			System.out.println(dp[V]);
		}
	}

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

poj 3181 Dollar Dayz 钱币兑换问题 大数/高精度 完全背包

poj 3181 Dollar Dayz 钱币兑换问题大数/高精度完全背包