※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ Problem Set from DPL 問0~4」の編集履歴(バックアップ)一覧に戻る

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 03:46:40) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*Combinatorial - Coin Changing Problem
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A
+金額を払うのに必要な最小コイン枚数をDPで解く問題。
 
+ #include<stdio.h>
+ #include<vector>
+ 
+ int main(){
+ 	int n,m,memo[50001]={0};
+ 	scanf("%d %d",&n,&m);
+ 	int coin;
+  	for(int i=0;i<m;i++){
+ 		scanf("%d",&coin);
+ 		for(int j=0;j+coin<=n;j++){
+ 			if(memo[j]==0&&j>0)continue;
+ 			if(memo[j+coin]==0||memo[j+coin]>memo[j]+1){
+ 				memo[j+coin]=memo[j]+1;
+ 			}
+ 		}
+  	}
+ 	printf("%d\n",memo[n]);
+ }