「aoj2231~2240」の編集履歴(バックアップ)一覧に戻る

aoj2231~2240 - (2013/02/08 (金) 18:55:07) の最新版との変更点

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

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

 *2233 Carrot Tour
 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2233
 兎が都市を回って人参をもらってくる問題。
 
 解法
 兎が前にいた都市今いる都市の組を点に見立ててグラフとして解きます。
-人参の個数を一つずつインクリメントしながら人参n個で前にいた都市a今いる都市bからn+1個に至る場合を段階的に動的計画法で計算していけば答えが出ます。
+人参の個数を一つずつインクリメントしながら人参n個で前にいた都市a今いる都市bとして動的計画法で計算していけば答えが出ます。
 もっと速度が出るかと思ったら意外と速度が出ませんでした。
 
 
 
 
 
  #include<stdio.h>
  #include<vector>
  #include<queue>
  #include<map>
  #include<math.h>
  #include<iostream>
  
  struct rMove{
  	int oldCity,nowCity;
  	long double len;
  };
  
  int main(){
  	long double xs[21],ys[21];
  	int n;
  	long double r,theta;
  	scanf("%d",&n);
 	if(n==1){
  		printf("0\n");
  		return 0;
  	}
  	std::cin>>r>>theta;
  	theta=cos(theta/180.0*M_PI);
  	for(int i=0;i<n;i++){
  		std::cin>>xs[i]>>ys[i];
  	}
  	std::vector<int> moveOKs[21][21];//moveOKs[前いた都市][今いる都市]="次にいける都市のリスト"
  	long double dx1,dx2,dy1,dy2;
  	for(int i=0;i<n;i++){
  		//前の都市
  		for(int j=0;j<n;j++){
  			//今いる都市
  			if(i==j)continue;
  			for(int k=0;k<n;k++){
  				//次の都市
  				if(i==k||j==k)continue;
  				dx1=xs[j]-xs[i];
  				dy1=ys[j]-ys[i];
  				dx2=xs[k]-xs[j];
  				dy2=ys[k]-ys[j];
  				double cos1=(dx1*dx2+dy1*dy2)/(hypot(dx1,dy1)*hypot(dx2,dy2));
  				if(cos1>=theta&&hypot(dx2,dy2)<=r){
  					moveOKs[i][j].push_back(k);
  				}
  			}
  		}
  	}
  	std::queue<rMove> qu;
   	rMove rm;
  	rm.oldCity=0;
  	for(int i=1;i<n;i++){
  		rm.len=hypot(xs[i]-xs[0],ys[i]-ys[0]);
  		rm.nowCity=i;
  		if(rm.len<=r){
  			qu.push(rm);
  		}
  	}
  	int ans=0;
  	std::map<int,double> getMemo[21];//[前にいた都市][今いる都市]=最短移動距離
  	while(qu.empty()==false){
  		double len;
  		ans++;
  		while(qu.empty()==false){
   			rm=qu.front();
  			qu.pop();
  			if(rm.len>r)continue;
  			for(int i=0;i<moveOKs[rm.oldCity][rm.nowCity].size();i++){
  				int no=moveOKs[rm.oldCity][rm.nowCity][i];
  				double len=rm.len+hypot(xs[rm.nowCity]-xs[no],ys[rm.nowCity]-ys[no]);
  				if(len>r)continue;
  				if(getMemo[rm.nowCity].find(no)==getMemo[rm.nowCity].end()||getMemo[rm.nowCity][no]>len){
  					getMemo[rm.nowCity][no]=len;
  				}
   			}
  		}
  		for(int i=0;i<n;i++){
  			for(int j=0;j<n;j++){
  				if(getMemo[i].find(j)!=getMemo[i].end()){
  					rm.oldCity=i;
  					rm.nowCity=j;
  					rm.len=getMemo[i][j];
  					qu.push(rm);
   				}
  			}
  		}
  		for(int i=0;i<n;i++)getMemo[i].clear();
  	}
  	
  	printf("%d\n",ans);
  }