3181-Dollar Dayz
問題(外部リンク)
実装の概要
動的計画法で解きます。
決まった合計金額における品物の買い方のパターン数を問う問題ですが、例えば合計が$5なら「$1 $1 $1 $2」のように必ず安い順に購入すると決めると考えやすくなります。そこでdp[i][j]を「一番高い単価がiで、合計金額がjとなるパターン数」と定義すると、dp[i][j] = dp[0][j - i]+dp[1][j - i]+...+dp[i][j - i]となります。
注意点ですが、この問題ではN<=1000、K<=100となっており、long型でもオーバーフローを起こすためBigIntegerクラスを使います。intやlongの足し算よりも時間はかかりますが制限時間には間に合います。
なお、工夫次第では配列の再利用などにより効率化を図れる可能性があります。
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] tmpArray = br.readLine().split(" "); int n = Integer.parseInt(tmpArray[0]); int k = Integer.parseInt(tmpArray[1]); //dp[i][j] 一番高い単価がiで合計金額がjのパターン数 BigInteger dp[][] = new BigInteger[k+1][n+1]; //初期化 for(int i = 0; i <= k ; i++){ for(int j = 0; j <= n; j++){ //一番高い単価がiで合計金額もiなのは明らかに1通り if(i == j){ dp[i][i] = new BigInteger("1"); } else { dp[i][j] = new BigInteger("0"); } } } for(int i = 1; i <= k; i++){ for(int j = i + 1; j <= n; j++){ for(int l = 1; l <= i; l++){ dp[i][j] = dp[i][j].add(dp[l][j - i]); } } } //debug // for(int i = 1; i <= k; i++){ // for(int j = 1; j <= n; j++){ // System.out.print(dp[i][j]+" "); // } // System.out.println(); // } // System.out.println(); BigInteger sum = new BigInteger("0"); for(int i = 1; i <= k; i++){ sum = sum.add(dp[i][n]); } System.out.println(sum); } }