首页 > 专题系列 > Java解POJ > POJ 3181 Dollar Dayz [解题报告] Java
2013
11-12

POJ 3181 Dollar Dayz [解题报告] Java

Dollar Dayz

问题描述 :

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).

输入:

A single line with two space-separated integers: N and K.

输出:

A single line with a single integer that is the number of unique ways FJ can spend his money.

样例输入:

5 3

样例输出:

5

解题代码:

//* @author:alpc12
import java.io.*;
import java.util.*;
import java.math.*;


public class Main {
 final int N = 1010;
 BigInteger[] dp = new BigInteger[N];

 void run() {
  Scanner cin = new Scanner(System.in);
  while(cin.hasNext()) {
    int i, j;
    int n = cin.nextInt(), k = cin.nextInt();
    for(i = 1; i <= n; ++i)
	dp[i] = BigInteger.ZERO;
	dp[0] = BigInteger.ONE;
	for(i = 1; i <= k; ++i) {
	  for(j = 0; j + i <= n; ++j)
	    dp[j+i] = dp[j+i].add(dp[j]);
	}
	System.out.println(dp[n]);
   }
 }

 public static void main(String[] args) {
    new Main().run();

 }

}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!