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

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

AOJ1081~1090 - (2012/07/30 (月) 05:46:13) のソース

*1084 
数字を並べたカードを入れ替えて連続した数の掛け算を行うとき最大の数を求める問題。

仮説
この問題はある2枚のカードを入れ替えるというよりも、注目しているk枚の範囲のカードのうち一番小さいカードを、k枚の外側にある一番大きなカードと入れ替えたらどうなるかという点に注目して解く。
問題はカードの入れ替えを何度も行ってもよいらしいということです。
つまり途中までカードの得点を下げて最後に一気に成績点を上げる可能性が残されています。





*1085 Spellcasters
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1085
魔法使いがペアを組んで戦うとき相手に勝てるペアの組み方がいくらあるかを求める問題。

各魔法使いについて自分とペアを組める人の最低値を二分探索で探すだけです。
後はそれより大きな人とは必ずペアが組めるので足しこめば計算終了です。


 #include<stdio.h>
 #include<algorithm>
 #include<vector>
 struct wiz{
	int no,r;
	bool operator<(const wiz& w)const{
		return r<w.r;
	}
 };
 void calc(int n,int s){
	std::vector<wiz> vs;
	std::vector<wiz>::iterator it;
	int r;
	wiz w;
	for(int i=0;i<n;i++){
		scanf("%d",&r);
		w.r=r;
		vs.push_back(w);
	}
	std::sort(vs.begin(),vs.end());
	for(int i=0;i<n;i++)vs[i].no=i;
	int ans=0,m;
	for(int i=0;i<n-1;i++){
		w.r=s-vs[i].r;
		it=std::upper_bound(vs.begin(),vs.end(),w);
		if(it==vs.end())continue;
		m=std::max((*it).no,i);
		if(i==m)m++;//自分自身とはペアは組めないのでひいておく
		ans+=n-m;
	}
	
	printf("%d\n",ans);
 }
 int main(){
	int n,s;
	while(1){
		scanf("%d %d",&n,&s);
		if(n==0&&s==0)break;
		calc(n,s);
	}
 }




*1086 Live Schedule
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1086
ツアーのスケジュールデータから利益を最大化するツアー計画を立てた時の最大利益を求める問題。

日数、連続公演の数、疲労度を基準にした動的計画法で合格。
暑い、、夏バテ、アイスがないなら死んでるな。



 #include<stdio.h>
 #include<string.h>
 #include<algorithm>
 int memo[32][7][52];//日数、連続公演の数、疲労度
 void setData(int c,int d,int w,int x){	
	int Es[32][32];//売り上げ[地域の数][日数]
	int Fs[32][32];//疲労度[地域の数][日数]
	memset(memo,-1,sizeof(memo));
	//収益の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Es[i][j]);
		}
	}
	//疲労度の読み込み
	for(int i=0;i<c;i++){
		for(int j=0;j<d;j++){
			scanf("%d",&Fs[i][j]);
		}
	}
	//日数、連続公演回数、疲労度を基準に動的計画法を適用する
	int ans=0,sumE,sumF;
	memo[0][0][0]=0;
	for(int i=0;i<d;i++){
		for(int j=0;j<=x;j++){
			for(int k=0;k<=w;k++){
				//日数、連続公演回数、疲労度のループ
				if(memo[i][j][k]==-1)continue;
				memo[i+1][j][k]=std::max(memo[i][j][k],memo[i+1][j][k]);//この日は公演を行わない
				ans=std::max(memo[i+1][j][k],ans);
				for(int l=0;l<c;l++){
					sumE=memo[i][j][k];
					sumF=k;
					for(int m=l;m>=0;m--){
						if(Es[m][i]==0)break;
						sumE+=Es[m][i];
						sumF+=Fs[m][i];
						if(w<sumF)break;
						int add=(m!=l?1:0);
						if(add==1&&x==j)break;
						memo[i+1][j+add][sumF]=std::max(sumE,memo[i+1][j+add][sumF]);
						ans=std::max(memo[i+1][j+add][sumF],ans);
					}
				}
			}
		}
	}
	for(int j=0;j<=x;j++){
		for(int k=0;k<=w;k++){
			ans=std::max(memo[d][j][k],ans);
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	int c,d,w,x;
	while(1){
		scanf("%d %d %d %d",&c,&d,&w,&x);
		if(c==0&&d==0&&w==0&&x==0)break;
		setData(c,d,w,x);
	}
 }