POI: Ploughing

https://szkopul.edu.pl/problemset/problem/6YiP6JA5U15hY94pLwuHoYPg/site/?key=statement

実践的アルゴリズム貪欲編です。

少し観察すると(列をstripする回数==M)または(行をstripする回数==N)が成立することがわかります。
対称なので(列をstripする回数==M)とします。
行について上からstripする回数と下からstripする回数を固定すれば、列は貪欲的にstripを行えます。
なのでdp[上からstripする回数][下からstripする回数]=make_pair(左から何回stripできるか,右から何回stripできるか) を埋めればよくて、それはならし計算量O((N+M)^2)で行うことができます。

ほそながいところより難しいということになっていましたが、こっちの方がまだ考えやすいと思いました。

int K, N, M;
int XS[2010][2010];//x-axis way sum,[ )
int YS[2010][2010];//y-axis way sum,[ )
pi dp[2010][2010];//[0, l) and [r, N)

pi narrow(int xl, int xr, int yl, int yr) { //xl, xr:constant, narrow yl and yr. [0, yl) and [yr, M)
	while(yr - yl >= 1 && XS[xr][yl] - XS[xl][yl] <= K) {
		yl++;
	}
	while(yr - yl >= 1 && XS[xr][yr - 1] - XS[xl][yr - 1] <= K) {
		yr--;
	}
	return pi(yl, yr);
}

int solve_sub() {
	int res = inf;
	rep(i, 0, N + 1) 
		rep(j, i + 1, N + 1) dp[i][j] = pinf;
	dp[0][N] = narrow(0, N, 0, M);
	rep(i, 0, N + 1) {
		rer(k, N + 1, 2) {
			int j = i + k;
			if(j > N || dp[i][j] == pinf) continue;
			int yl = dp[i][j].fst, yr = dp[i][j].sec;
			if(dp[i + 1][j] == pinf && YS[i][yr] - YS[i][yl] <= K) {
				dp[i + 1][j] = narrow(i + 1, j, yl, yr);
			}
			if(dp[i][j - 1] == pinf && YS[j - 1][yr] - YS[j - 1][yl] <= K) {
				dp[i][j - 1] = narrow(i, j - 1, yl, yr);
			}
		}
	}
	rep(i, 0, N + 1) {
		rep(j, 0, N + 1) {
			if(dp[i][j] == pinf) continue;
			if(dp[i][j].sec - dp[i][j].fst == 0) {
				MIN(res, M + i + N - j);
			}
		}
	}
	return res;
}

void solve() {
	cin >> K >> M >> N;
	rep(i, 0, N) {
		rep(j, 0, M) cin >> XS[i + 1][j];
	}
	rep(i, 0, N) 
		rep(j, 0, M) YS[i][j + 1] = YS[i][j] + XS[i + 1][j];
	rep(j, 0, M)
		rep(i, 1, N + 1) XS[i + 1][j] += XS[i][j];
	int res = inf;
	MIN(res, solve_sub());
	rep(i, 0, max(N, M) + 1) {
		rep(j, i + 1, max(N, M) + 1) {
			swap(XS[i][j], XS[j][i]);
			swap(YS[i][j], YS[j][i]);
		}
	}
	swap(XS, YS);
	swap(N, M);
	MIN(res, solve_sub());
	cout << res << "\n";
}

無駄にMLEが厳しいのやめて…