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が厳しいのやめて…