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

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 04:19:49) の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]);
  }
 
 
 
 *Combinatorial - 0-1 Knapsack Problem
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_B
 重さ付きナップザック問題。
  
  #include<stdio.h>
  #include<vector>
  
  int main(){
   	int n,W,memo[10001]={0};
  	scanf("%d %d",&n,&W);
  	int v,w,sum=0,ans=0;
  	while(n--){
  		scanf("%d %d",&v,&w);
  		if(sum+w>W)sum=W-w;
  		for(int j=sum;j>=0;j--){
   			if(memo[j+w]<memo[j]+v)memo[j+w]=memo[j]+v;
  		}
   		sum+=w;
  	}
          for(int i=0;i<=W;i++)if(ans<memo[i])ans=memo[i];
  	printf("%d\n",ans);
+ }
+
+
+
+
+*Combinatorial - Longest Increasing Subsequence
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_D
+数列の中の最長増加部分列の長さをこたえる問題。
+ちょっと邪道な解法かも。
+
+ #include<stdio.h>
+ #include<map>
+ std::map<int,int> memo;
+  
+ i nt main(){
+ 	int n,a;
+ 	std::map<int,int>::reverse_iterator rIt;
+ 	scanf("%d",&n);
+ 	memo[0]=-1;
+ 	while(n--){
+ 		scanf("%d",&a);
+ 		for(rIt=memo.rbegin();rIt!=memo.rend();rIt++){
+ 			if((*rIt).second<a){
+  				memo[(*rIt).first+1]=a;
+ 				break;
+ 			}
+ 		}
+ 		if(memo.find(1)==memo.end() || memo[1]>a){
+ 			memo[1]=a;
+ 		}
+  	}
+ 	rIt=memo.rbegin();
+ 	printf("%d\n",(*rIt).first);
  }