Dollar Dayz [dp + java高精度]

Dollar Dayz

ドルdayz

制限時間： 1000MS		メモリ制限： 65536K
総提出数： 8535		承認済み： 3191

説明

ファーマージョンはカウストアのダラーデイズに行き、販売されているツールの数に制限がないことを発見しました。彼の最初の訪問中、ツールは1ドル、2ドル、3ドルでさまざまに販売されています。ファーマージョンはちょうど5ドルを使うことができます。彼は5つのツールをそれぞれ1ドルで購入するか、1つのツールを3ドルで購入し、さらに1つのツールを2ドルで購入できます。もちろん、FJがすべてのお金をツールに費やすことができる合計5つの異なる方法のための他の組み合わせがあります。どうぞ：

import java.util.* import java.math.* public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in) BigInteger dp[][] = new BigInteger[1005][105] int n,k while(cin.hasNext()){ n = cin.nextInt() k = cin.nextInt() for(int i=0i<=ni++){ for(int j=0j<=kj++){ dp[i][j]=new BigInteger('0') } } dp[0][0]=new BigInteger('1') for(int i=1i<=ni++){ for(int j=1j<=k && j<=ij++){ for(int p=0p=0){ dp[i][j]=dp[i][j].add(dp[i-j][p]) } } //System.out.println(dp[i][j]) } } BigInteger ans = new BigInteger('0') for(int i=1i<=ki++){ ans=ans.add(dp[n][i]) } System.out.println(ans) } } } FJがNドルを費やすことができる方法の数を計算するよりもプログラムを書く（1<= N <= 1000) at The Cow Store for tools on sale with a cost of $1..$K (1 <= K <= 100).

入力

NとKの2つのスペースで区切られた整数を持つ1行。

出力

FJが彼のお金を使うことができるユニークな方法の数である単一の整数を持つ単一の行。

サンプル入力

 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

サンプル出力

5 3

ソース

USACO 20061月シルバー

5