「aoj2221～2230」の編集履歴（バックアップ）一覧に戻る

aoj2221～2230 - (2012/07/08 (日) 08:17:00) のソース

*2221　　KULASIS
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2221
成績表を不正に操作して最高の成績を求める問題。
この問題他の方は行列概念を使って解いてるらしい。
私は一段ずつ確定していく素朴な動的計画法でアセプト。
ある段までのスイッチの押しが決まったらそこより上の段は上の段の合計スコア以外計算に関係がない。
ことを利用してシンプルに解いたら、速度が出なかった。
考えたらどの段も1024通り全部が出てくる可能性があるから配列を使うべきでほとんどMapを使う意味がないと気付いたのはアセプトした後だったりしました。


 #include<stdio.h>
 #include<map>
 #include <algorithm>
 struct myLine{
	int num[5];//今操作中の行
	int next[5];//次の行
	bool operator<(const myLine& l)const{
		for(int i=0;i<5;i++){
			if(next[i]!=l.next[i])return next[i]<l.next[i];
		}
		return false;
	}
	void click(int c){
		//0～3までボタンが押された
		if(num[c]!=0)	 num[c]=num[c]%4+1;
		if(num[c+1]!=0) num[c+1]=num[c+1]%4+1;
		if(next[c]!=0)	 next[c]=next[c]%4+1;
		if(next[c+1]!=0)next[c+1]=next[c+1]%4+1;
	}
	int score(){
		int s=0,n;
		for(int i=0;i<5;i++){
			n=num[i];
			s+=(n==4)*80+(n==3)*70+(n==2)*60;
		}
		return s;
	}
	void setNext(int nextmyLine[5]){
		for(int i=0;i<5;i++){
			num[i]	=next[i];
			next[i]	=nextmyLine[i];
		}
	}
	
 };
 int data[6][6];//初期データ
 std::map<myLine,int> memo[6];//一行ずつ処理していく
 int ans;
 void saiki(myLine& l,int row,int col,int score){
	if(col==4){
		score+=l.score();		
		if(row==4){
			//4行目のスイッチ操作が終わったなら
			myLine nextL=l;
			nextL.setNext(data[row+1]);
			ans=std::max(score+nextL.score(),ans);
		}else{
			//でないなら
			if(memo[row].find(l)==memo[row].end()){
				memo[row][l]=score;
			}else{
				memo[row][l]=std::max(memo[row][l],score);
			}
		}
	}else{
		for(int i=0;i<4;i++){
			l.click(col);
			saiki(l,row,col+1,score);
		}
	}
 }
 void calc(){
	ans=0;
	for(int i=0;i<25;i++){
		int x=i%5;
		int y=i/5;
		memo[y].clear();
		scanf("%d",&data[y][x]);
	}
	myLine l;
	l.setNext(data[0]);
	memo[0][l]=0;
	std::map<myLine,int>::iterator it;
	for(int r=1;r<5;r++){
		for(it=memo[r-1].begin();it!=memo[r-1].end();it++){
			l=(*it).first;
			l.setNext(data[r]);
			saiki(l,r,0,(*it).second);
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	
	int n;
	scanf("%d",&n);
	while(n--){
		calc();
	}
 }