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

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

AOJ181~190 - (2011/08/29 (月) 13:41:23) のソース

*0181 Persistence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181
n巻そろった本を1巻から順にm段の本棚に右下から詰めて入れます。
格段の本の幅が小さくなるようないれ方をした時、格段の本の幅の最大の幅がどれくらいとなるか答えよ。
本を詰める順番は1巻から順にし順番を違えないとする。

解法
i段目までm冊目までの本を入れた時、どのような入れ方をしたにせよ、そこまでの本の幅が最小となる入れ方のみを残します。
この考え方で動的計画法で解きます。



 #include<stdio.h>
 #include<algorithm>
 void setData(int m,int n){
	int memo[21][102],w=0;
    for(int i=0;i<21;i++){
        for(int j=0;j<102;j++){
            memo[i][j]=2000000000;
        }
    }
	memo[0][0]=0;
	for(int i=0;i<n;i++){
		scanf("%d",&w);
		memo[0][i+1]=memo[0][i]+w;
	}
	int t1,t2;
	for(int i=1;i<m;i++){
		for(int j=0;j<n;j++){
			for(int k=j+1;k<=n;k++){
				t1=memo[i-1][j];
                t1=t1==2000000000?0:t1;
                t2=memo[0][k]-memo[0][j];
				t1=std::max(t1,t2);
				memo[i][k]=std::min(memo[i][k],t1);
			}
		}
	}
	printf("%d\n",memo[m-1][n]);
 }
 int main(){
	int m,n;
	while(1){
		scanf("%d %d",&m,&n);
		if(m==0 && n==0) break;
		setData(m,n);
	}
 }



----
*0182 Beaker
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0182
ビーカーからビーカーへ水を移して、全てのビーカーに一度ずつ水を入れれるかという問題。

解法
正答まであと少しのコードを書いています。
タイムリミッドを喰らうのでどう高速化しようか思案中です。


 #include<stdio.h>
 #include<map>
 #include<vector>
 int inBeakers[51];
 int okBeakers[51];
 int beakerSize[51];
 bool butBeakers[51];
 int n;
 bool allOK;
 int allCount;
 void saiki(int spentBeaker,int measure,int p){
	if(spentBeaker==allCount && measure==0){
		allOK=true;
		return;
	}else if(measure==0){
		std::vector<int> memo;
		for(int i=0;i<n;i++){
			if(inBeakers[i]>0 && butBeakers[i]==false){
				inBeakers[i]--;
				saiki(spentBeaker,beakerSize[i],n-1);
				if(allOK==true) return;
				butBeakers[i]=true;
				inBeakers[i]++;
				memo.push_back(i);
			}
		}
		for(int i=0;i<memo.size();i++){
			butBeakers[memo[i]]=false;
		}
	}else{
		for(int i=p;i>=0;i--){
			if(okBeakers[i]>0 && measure>=beakerSize[i]){
				okBeakers[i]--;
				inBeakers[i]++;
				saiki(spentBeaker+1,measure-beakerSize[i],i);
				if(allOK==true) return;
				inBeakers[i]--;
				okBeakers[i]++;
			}
		}
	}
 }
 void setData(){
	std::map<int,int> beakers;
	std::map<int,int>::iterator it;
	int t;
	allOK=false;
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		if(beakers.find(t)==beakers.end()){
			beakers[t]=1;
		}else{
			beakers[t]++;
		}
	}
	it=beakers.begin();
	allCount=n=0;
	while(it!=beakers.end()){
		okBeakers [n]=(*it).second;
		inBeakers [n]=0;
		butBeakers[n]=false;
		beakerSize[n]=(*it).first;
		allCount+=okBeakers[n];
		it++;
		n++;
	}
	okBeakers[n-1]--;
	if(n>1){
		saiki(1,beakerSize[n-1],n-1);
	}else{
		allOK=true;
	}
	printf("%s\n",allOK==true?"YES":"NO");
 }
 int main(){
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData();
	}
 }





----
*0184 Tsuruga Castle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0184
解法
何も考えずに集計するだけです。
10の倍数であることを利用して割ることで少しだけコードが短くなります。

 #include<stdio.h>
 int main(){
	int n,y,sums[7],i;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<7;i++)sums[i]=0;
		for(i=0;i<n;i++){
			scanf("%d",&y);
			y=y>60?60:y;
			sums[y/10]++;
		}
		for(i=0;i<7;i++){
			printf("%d\n",sums[i]);
		}
	}
 }