https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_h
お気持ちはわかるし、結構惜しいところまではいけるけど…
氷山を消すと、4辺全てに氷山がある長方形領域に分断されることがわかります。なのでそれにしたがってDPすればいいです。
といえば簡単なんですが、分断されるというアイディアに至るためにはたくさん図を描く必要があると思います。
僕は特殊な場合だけうまくいく方法を思いついたんですが、もちろんWAだし、アルゴリズムの正当性も全然証明できなくて途方に暮れてしまいました。
今回みたいな特に言い換えるパートもなく、何をやっているか正しく把握できるかが勝負になる問題は、ひたすら実験するのが吉みたいですね。
int N, M; int X, Y; int A[50][50]; int S[50][50]; int dp[50][50][50][50]; int get_sum(int x1, int y1, int x2, int y2) { return S[x2 + 1][y2 + 1] - S[x2 + 1][y1] - S[x1][y2 + 1] + S[x1][y1]; } void solve() { cin >> N >> M; rep(i, 0, N) { rep(j, 0, M) { char c; cin >> c; if(c == '+') A[i][j] = 0; else if(c == '#') A[i][j] = 1; else { A[i][j] = 0; X = i; Y = j; } } } rep(i, 0, N) { rep(j, 0, M) { S[i + 1][j + 1] = A[i][j] + S[i + 1][j] + S[i][j + 1] - S[i][j]; } } rep(x1, 0, N) { rep(y1, 0, M) { rep(x2, x1, N) { rep(y2, y1, M) { dp[x1][y1][x2][y2] = N * M; } } } } dp[0][0][N - 1][M - 1] = 0; rep(x1, 0, N) { rep(y1, 0, M) { rer(x2, N, x1) { rer(y2, M, y1) { rep(x, 0, x1 + 1) { rep(y, 0, y1 + 1) { MIN(dp[x1][y1][x2][y2], dp[x][y][x2][y2] + get_sum(x, y1, x1 - 1, y2) + get_sum(x1, y, x2, y1 - 1)); } } rep(x, x2, N) { rep(y, 0, y1 + 1) { MIN(dp[x1][y1][x2][y2], dp[x1][y][x][y2] + get_sum(x1, y, x2, y1 - 1) + get_sum(x2 + 1, y1, x, y2)); } } rep(x, 0, x1 + 1) { rep(y, y2, M) { MIN(dp[x1][y1][x2][y2], dp[x][y1][x2][y] + get_sum(x, y1, x1 - 1, y2) + get_sum(x1, y2 + 1, x2, y)); } } rep(x, x2, N) { rep(y, y2, M) { MIN(dp[x1][y1][x2][y2], dp[x1][y1][x][y] + get_sum(x2 + 1, y1, x, y2) + get_sum(x1, y2 + 1, x2, y)); } } } } } } int ans = N * M; rep(x1, 0, N) { rep(y1, 0, M) { rep(x2, x1, N) { rep(y2, y1, M) { if(!(x1 <= X && X <= x2 && y1 <= Y && Y <= y2)) continue; MIN(ans, dp[x1][y1][x2][y2] + get_sum(x1, y1, X, Y)); MIN(ans, dp[x1][y1][x2][y2] + get_sum(X, y1, x2, Y)); MIN(ans, dp[x1][y1][x2][y2] + get_sum(x1, Y, X, y2)); MIN(ans, dp[x1][y1][x2][y2] + get_sum(X, Y, x2, y2)); } } } } cout << ans << "\n"; }
