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

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

AOJ181~190 - (2011/08/24 (水) 15:06:21) の1つ前との変更点

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

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

 *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);
+	}
+ }
+
+
+
+
+
+
+
+----
+*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]);
+		}
 	}
  }