AOJ 1176 - Planning Rolling Blackouts

問題文 : 輪番停電計画

解法 :

$dp[sy][sx][gy][gx] := sy \leqq y \leqq gy,\ sx \leqq x \leqq gx$ を満たす区間でのグループの数の最大値と, 供給力の最大値として, メモ化再帰を行うと楽.
列 or 行を降りていき, 分割が不可能な域に達したらimpossible を表すような状態を返してやれば良い.

コード :

#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int h, w, s;
int p[32][32], sum[32][32];
pair<int, int> dp[32][32][32][32];

int getSum(int sy, int sx, int gy, int gx)
{
	int ret = sum[gy][gx];
	if (sy) ret -= sum[sy - 1][gx];
	if (sx) ret -= sum[gy][sx - 1];
	if (sy && sx) ret += sum[sy - 1][sx - 1];
	
	return (ret);
}

pair<int, int> calc(int sy, int sx, int gy, int gx)
{
	if (~dp[sy][sx][gy][gx].first) return (dp[sy][sx][gy][gx]);
	
	int cost = sum[h - 1][w - 1] - getSum(sy, sx, gy, gx);
	if (cost > s) return make_pair(0, -1);
	pair<int, int> res = make_pair(1, -cost);
	pair<int, int> a, b, c;
	
	for (int i = sy; i <= gy - 1; i++){
		a = calc(sy, sx, i, gx); b = calc(i + 1, sx, gy, gx);
		if (a.first == 0 || b.first == 0) continue;
		c = make_pair(a.first + b.first, min(a.second, b.second));
		if (res < c) res = c;
	}
	
	for (int i = sx; i <= gx - 1; i++){
		a = calc(sy, sx, gy, i); b = calc(sy, i + 1, gy, gx);
		if (a.first == 0 || b.first == 0) continue;
		c = make_pair(a.first + b.first, min(a.second, b.second));
		if (res < c) res = c;
	}
	
	return (dp[sy][sx][gy][gx] = res);
}

int main()
{
	while (scanf("%d %d %d", &h, &w, &s) && w){
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				scanf("%d", &p[i][j]);
		
		for (int i = 0; i < 32; i++)
			for (int j = 0; j < 32; j++)
				for (int k = 0; k < 32; k++)
					for (int l = 0; l < 32; l++)
						dp[i][j][k][l].first = dp[i][j][k][l].second = -1;
		
		memset(sum, 0, sizeof(sum));
		
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				sum[i][j] += p[i][j];
				if (i) sum[i][j] += sum[i - 1][j];
				if (j) sum[i][j] += sum[i][j - 1];
				if (i && j) sum[i][j] -= sum[i - 1][j - 1];
			}
		}
		
		pair<int, int> res = calc(0, 0, h - 1, w - 1);
		printf("%d %d\n", res.first, s + res.second);
	}
	
	return (0);
}