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

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

AOJ Problem Set from DPL 問0~4 - (2014/01/28 (火) 04:19:49) の最新版との変更点

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

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

 *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> memo;
-  
- i nt main(){
+ std::map<int,int> memo1;
+ int memo[100001]={0};
+ 
+ int main(){
  	int n,a;
- 	std::map<int,int>::reverse_iterator rIt;
+ 	std::map<int,int>::iterator it1,it2;
  	scanf("%d",&n);
- 	memo[0]=-1;
+ 	scanf("%d",&a);
+  	memo[0]=-1;
+ 	memo[1]=a;
+ 	n--;
+ 	memo1[-1]=0;
+ 	memo1[a]=1;
  	while(n--){
  		scanf("%d",&a);
- 		for(rIt=memo.rbegin();rIt!=memo.rend();rIt++){
- 			if((*rIt).second<a){
-  				memo[(*rIt).first+1]=a;
- 				break;
- 			}
+ 		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);
+  			}
  		}
- 		if(memo.find(1)==memo.end() || memo[1]>a){
- 			memo[1]=a;
+ 	}
+ 	int ans=1;
+ 	for(int i=100000;i>=0;i--){
+ 		if(memo[i]>0){
+  			ans=i;
+ 			break;
  		}
   	}
- 	rIt=memo.rbegin();
- 	printf("%d\n",(*rIt).first);
+ 	printf("%d\n",ans);
+ }
+
+
+
+
+*Permutation/Path - Traveling Salesman Problem
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_2_A
+巡回セールスマン問題。
+解法
+この問題とても奥深い研究結果がたくさんあるそうですが私は
+とりあえずこの問題が解ければいいやというスタンスでコードを書きました。
+1点訪れた集合から2点訪れた集合を
+2点訪れた集合から3点訪れた集合を、、、
+と続けるだけの単純な動的計画法です。
+
+
+
+ #include<stdio.h>
+ #include<map>
+ 
+ 
+ struct S{
+ 	int nowP,bits;
+ 	bool operator<(const S& s)const{
+ 		if(nowP!=s.nowP)return nowP<s.nowP;
+ 		return bits<s.bits;
+ 	}
+ };
+ 
+ const int NIL=-1;
+ int G[15][15];
+ 
+ 
+ int main(){
+ 	
+ 	std::map<S,int> now,next;
+ 	std::map<S,int>::iterator it;
+ 	int V,E,s,t,d;
+  	for(int i=0;i<15;i++){
+ 		for(int j=0;j<15;j++){
+ 			G[i][j]=-1;
+ 		}
+ 	}
+ 	scanf("%d %d",&V,&E);
+ 	for(int i=0;i<E;i++){
+ 		scanf("%d %d %d",&s,&t,&d);
+ 		G[s][t]=d;
+ 	}
+ 	S s1,s2;
+  	s1.nowP=0;
+ 	s1.bits=0;
+ 	now[s1]=0;
+ 	for(int i=0;i<V;i++){
+ 		for(it=now.begin();it!=now.end();it++){
+ 			s1=(*it).first;
+ 			for(int j=0;j<V;j++){
+ 				if(j==0&&i<V-1)continue;
+ 				int g=G[s1.nowP][j];
+  				if(g==-1)continue;
+ 				int addBit=(1<<j);
+ 				if((s1.bits&addBit)>0)continue;
+ 				g+=(*it).second;
+ 				s2.nowP=j;
+ 				s2.bits=(s1.bits|addBit);
+  				if(next.find(s2)==next.end() || next[s2]>g){
+ 					next[s2]=g;
+				}
+ 			}
+		}
+  		now.clear();
+ 		now.insert(next.begin(),next.end());
+ 		next.clear();
+ 	}
+ 	it=now.begin();
+  	int ans=-1;
+ 	if(it!=now.end())ans=(*it).second;
+ 	printf("%d\n",ans);
  }