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

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

AOJ181~190 - (2011/08/24 (水) 11:24:56) の編集履歴(バックアップ)


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);
}
}