2012-12-30

■ SRM525 Div2 600の解法3っぽいソース(O(C*R*R)) 00:47

#include 
#include 
#include 
using namespace std;
class DropCoins{
public:
int getMinimum(vector  board, int K){
int rui[31][31]={};
for(int i=1;i<=board.size();i++){
	if(board[i-1][0]=='o'){
		rui[i][1]=rui[i-1][1]+1;
	}else{
		rui[i][1]=rui[i-1][1];
	}
}
for(int i=1;i<=board[0].size();i++){
	if(board[0][i-1]=='o'){
		rui[1][i]=rui[1][i-1]+1;
	}else{
		rui[1][i]=rui[1][i-1];
	}
}
for(int i=2;i<=board.size();i++){
	for(int j=2;j<=board[0].size();j++){
		if(board[i-1][j-1]=='o'){
			rui[i][j]=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1]+1;
		}else{
			rui[i][j]=rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1];
		}
	}
}
int ans=10000000;
	for(int i=1;i<=board.size();i++){
		for(int j=i;j<=board.size();j++){
			int st=1,en=1;
			for(;;){
				int s=0;
				while(s<=K && en<=board[0].size()){
					s=rui[j][en]-rui[j][st-1]-rui[i-1][en]+rui[i-1][st-1];
					if(s<=K){
						en++;
					}
				}
				en--;
				if(rui[j][en]-rui[j][st-1]-rui[i-1][en]+rui[i-1][st-1]==K){
					int q=i-1;
					int r=board.size()-j;
					int p=min(q,r);
					int s=st-1;
					int t=board[0].size()-en;
					int w=min(s,t);
					ans=min(ans,(q+r+p+s+t+w));
				}
				en++;
				st++;
				if(en==board[0].size()+1) break;
			}
		}
	}
if(ans==10000000){
	return -1;
}else{
	return ans;
}
}
};

求めたいのは最短のスライド数なので、同じ縦幅で右の辺が決まっている状態では、左の辺は出来るだけ左にあった方がよい。

だから、endを固定しstartを動かす、という操作は必要ない。

必要なのは、含まれるコイン数がKを超えるまでendを動かし、超えたらendを-1する操作のみ。

つまり、endを動かし->start,endをともに+1するという尺取りのようなことをするとO(C*R^2)でできる。

ツイートする