AOJ 1176 Planning Rolling Blackouts

問題文: Planning Rolling Blackouts | Aizu Online Judge

現在見ている区間の上下左右の端で状態数32^4くらいでメモ化再帰った。

漸化式とかよく分からないのでソースを見てください。

二次元累積和使うと早いヨ!

一番面倒くさいのは、その中でさらに予備電力？が最大になるようなものを取らなきゃいけないということ。とりあえずpair使って実装してみた。pair使うと最大のグループ数を優先しつつ、予備電力も最大なものを取ってくれるので。

#include <iostream>
#include <cstring>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define num first
#define energy second
#define INF (9999)
typedef pair<int,int> pii;

int H , W , S;
int mat[40][40];
pii dp[40][40][40][40];

//[x1,x2) & [y1,y2)であるような区間を与えると部分和を計算する。
int count(int x1,int y1,int x2,int y2){
	return mat[y2-1][x2-1] - mat[y2-1][x1-1] - mat[y1-1][x2-1] + mat[y1-1][x1-1];
}

// [x1,x2) & [y1,y2)であるような区間を見ている。(重要)
pii dfs(int x1 , int y1 , int x2 , int y2){
	if(~dp[x1][y1][x2][y2].num) return dp[x1][y1][x2][y2];

	//現在の区間だけを停電させたとき、必要になる電源量がSを越えていたら駄目
	if(mat[H][W] - count(x1,y1,x2,y2) > S) return mp(-INF,INF);
	
	//今見ている区間を分割しなかった場合を初期値にしている。
	pii ans = mp( 1 , S - ( mat[H][W] - count(x1,y1,x2,y2) ) );
	
	for(int i = x1+1 ; i < x2 ; i++){
		pii A = dfs(x1,y1,i,y2);
		pii B = dfs(i,y1,x2,y2);
		pii get = mp( A.num + B.num , min(A.energy,B.energy) );
		ans = max( ans , get);
	}
	for(int i = y1+1 ; i < y2 ; i++){
		pii A = dfs(x1,y1,x2,i);
		pii B = dfs(x1,i,x2,y2);
		pii get = mp( A.num + B.num , min(A.energy,B.energy) );
		ans = max( ans , get);
	}
	
	return dp[x1][y1][x2][y2] = ans ;
}

int main(){
	int t;
	while(cin >> H >> W >> S , H || W || S ){
		memset(mat,0,sizeof(mat));
		
		for(int i = 0 ; i < 40 ; i++)
			for(int j = 0 ; j < 40 ; j++)
				for(int k = 0 ; k < 40 ; k++)
					for(int l = 0 ; l < 40 ; l++)
						dp[i][j][k][l] = mp(-1,-1);
		//入力 + 累積和化
		for(int i = 1 ; i <= H ; i++)
			for(int j = 1 ; j <= W ; j++)
				cin >> t , mat[i][j] = t + mat[i][j-1];
		
		for(int i = 1 ; i <= H ; i++)
			for(int j = 1 ; j <= W ; j++)
				mat[i][j] += mat[i-1][j];
		
		
		pii result = dfs(1,1,W+1,H+1);
		
		cout << result.num << " " << result.energy << endl;
	}
}