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

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

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 07:19:39) のソース

*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
数列の中の最長増加部分列の長さをこたえる問題。
最初に書いたコードが尾所方ので書き直したが2倍程度しか早くならなかった。
ある部分列があってそれが例えば
1,2,5
1,3
1,7
1,11
で次の数が8なら
1,2,5,8以外は考慮する意味がない。
という視点で計算量を切り落としていけばまあ平凡なタイムを出せます。



 #include<stdio.h>
 #include<map>
 std::map<int,int> memo1;
 int memo[100001]={0};
 
 int main(){
 	int n,a;
 	std::map<int,int>::iterator it1,it2;
 	scanf("%d",&n);
 	scanf("%d",&a);
  	memo[0]=-1;
 	memo[1]=a;
 	n--;
 	memo1[-1]=0;
 	memo1[a]=1;
 	while(n--){
 		scanf("%d",&a);
 		it1=it2=memo1.lower_bound(a);
 		it2--;
 		if(it1==memo1.end()){
 			memo[(*it2).second+1]=a;
 			memo1[a]=(*it2).second+1;
 		}else{
 			if((*it2).first<a&&a<(*it1).first){
 				int num1=(*it1).first;
 				int count1=(*it1).second;
 				memo[count1]=a;
 				memo1[a]=count1;
 				memo1.erase(num1);
  			}
 		}
 	}
 	int ans=1;
 	for(int i=100000;i>=0;i--){
 		if(memo[i]>0){
  			ans=i;
 			break;
 		}
  	}
 	printf("%d\n",ans);
 }