[BZOJ1177][Apio2009]Oil

試題描述

采油區(qū)域 Siruseri政府決定將石油資源豐富的Navalur省的土地拍賣給私人承包商以建立油井。被拍賣的整塊土地為一個(gè)矩形區(qū)域，被劃分為M×N個(gè)小塊。 Siruseri地質(zhì)調(diào)查局有關(guān)于Navalur土地石油儲量的估測數(shù)據(jù)。這些數(shù)據(jù)表示為M×N個(gè)非負(fù)整數(shù)，即對每一小塊土地石油儲量的估計(jì)值。 為了避免出現(xiàn)壟斷，政府規(guī)定每一個(gè)承包商只能承包一個(gè)由K×K塊相連的土地構(gòu)成的正方形區(qū)域。 AoE石油聯(lián)合公司由三個(gè)承包商組成，他們想選擇三塊互不相交的K×K的區(qū)域使得總的收益最大。 例如，假設(shè)石油儲量的估計(jì)值如下： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9 如果K = 2, AoE公司可以承包的區(qū)域的石油儲量總和為100, 如果K = 3, AoE公司可以承包的區(qū)域的石油儲量總和為208。 AoE公司雇傭你來寫一個(gè)程序，幫助計(jì)算出他們可以承包的區(qū)域的石油儲量之和的最大值。

輸入

輸入第一行包含三個(gè)整數(shù)M, N, K，其中M和N是矩形區(qū)域的行數(shù)和列數(shù)，K是每一個(gè)承包商承包的正方形的大小（邊長的塊數(shù)）。接下來M行，每行有N個(gè)非負(fù)整數(shù)表示這一行每一小塊土地的石油儲量的估計(jì)值

輸出

輸出只包含一個(gè)整數(shù)，表示AoE公司可以承包的區(qū)域的石油儲量之和的最大值。

輸入示例

9 9 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9

輸出示例

208

數(shù)據(jù)規(guī)模及約定

0 < n, m < 2501, 答案不超過int, 0 < k < min{ n, m }且保證有方案

題解

馬丹智障題。。。我來吐槽一下：

1.) 這題是一道惡心dp題（我分了14種情況討論）

2.) 這題大視野題面上沒有范圍，并且此題“討論”中所發(fā)的范圍是錯(cuò)的！

3.) 這題數(shù)據(jù)有問題，不能用任何讀入優(yōu)化

4.) 這題卡內(nèi)存

#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <stack> #include <vector> #include <queue> #include <cstring> #include <string> #include <map> #include <set> using namespace std;#define maxn 2505 #define LL int #define h f[0] #define t g[0] int n, m, K; LL S[maxn][maxn], f[2][maxn][maxn], g[2][maxn][maxn];LL sum(int x1, int y1, int x2, int y2) { return S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]; }int main() { // freopen("data.in", "r", stdin);scanf("%d%d%d", &n, &m, &K); // n = read(); m = read(); K = read();LL ans = 0;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++) {int tmp; scanf("%d", &tmp);S[i][j] = S[i-1][j] - S[i-1][j-1] + S[i][j-1] + tmp;}f[0][K][K] = S[K][K];for(int i = K; i <= n; i++)for(int j = K; j <= m; j++) {f[0][i][j] = max(max(f[0][i-1][j], f[0][i][j-1]), sum(i-K, j-K, i, j));f[1][i][j] = max(max(f[1][i-1][j], f[1][i][j-1]), sum(i-K, j-K, i, j) + max(f[0][i-K][j], f[0][i][j-K]));}g[0][n-K+1][m-K+1] = sum(n-K, m-K, n, m);for(int i = n-K+1; i; i--)for(int j = m-K+1; j; j--) {g[0][i][j] = max(max(g[0][i+1][j], g[0][i][j+1]), sum(i-1, j-1, i+K-1, j+K-1));g[1][i][j] = max(max(g[1][i+1][j], g[1][i][j+1]), sum(i-1, j-1, i+K-1, j+K-1) + max(g[0][i+K][j], g[0][i][j+K]));}for(int i = 1; i <= n-K+1; i++)for(int j = 1; j <= m-K+1; j++) {LL tmp = sum(i-1, j-1, i+K-1, j+K-1);ans = max(ans, tmp + f[1][i-1][m]);ans = max(ans, tmp + f[1][n][j-1]);ans = max(ans, tmp + g[1][1][j+K]);ans = max(ans, tmp + g[1][i+K][1]);ans = max(ans, tmp + f[0][i-1][j+K-1] + g[0][1][j+K]);ans = max(ans, tmp + f[0][i-1][m] + g[0][i][j+K]);ans = max(ans, tmp + f[0][i-1][m] + g[0][i+K][1]);ans = max(ans, tmp + f[0][i+K-1][j-1] + g[0][i+K][1]);ans = max(ans, tmp + f[0][n][j-1] + g[0][i+K][j]);ans = max(ans, tmp + f[0][n][j-1] + g[0][1][j+K]);}memset(h, 0, sizeof(h));h[K][m-K+1] = sum(0, m-K, K, m);for(int i = K; i <= n; i++)for(int j = m-K+1; j; j--)h[i][j] = max(max(h[i-1][j], h[i][j+1]), sum(i-K, j-1, i, j+K-1));memset(t, 0, sizeof(t));t[n-K+1][K] = sum(n-K, 0, n, K);for(int i = n-K+1; i; i--)for(int j = K; j <= m; j++)t[i][j] = max(max(t[i+1][j], t[i][j-1]), sum(i-1, j-K, i+K-1, j));for(int i = 1; i <= n-K+1; i++)for(int j = 1; j <= m-K+1; j++) {LL tmp = sum(i-1, j-1, i+K-1, j+K-1);ans = max(ans, tmp + t[i+K][m] + h[i+K-1][j+K]);ans = max(ans, tmp + t[i+K][j+K-1] + h[n][j+K]);ans = max(ans, tmp + t[1][j-1] + h[i-1][j]);ans = max(ans, tmp + t[i][j-1] + h[i-1][1]);}printf("%d\n", ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xiao-ju-ruo-xjr/p/5424556.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ1177][Apio2009]Oil的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。