[APIO2009]采油区域

OI 题解

这个题要求三个不相交$k*k$区域权值和最大，这样的话，不难想到先计算出来每个可能的$k*k$区域，即利用前缀和的思想。

又有三个不相交的正方形只有6种相对位置关系:

分六种情况讨论即可。

如果预先处理出某个点左上、左下、右上、右下部分的最大区域，对于左边4种情况，枚举交点位置即可，对于另外两种情况，可以在固定中间区域边界线的情况下枚举中间的矩形在哪个位置。（具体处理方法见代码）

代码

#include<cstdio>
#include<algorithm>
using std::max;
// 为了减少代码量
#define REP(i, j, k) for (int i = (j); i <= (k); ++i)
#define DEC(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N  = 1500 + 10;
ll a[N][N], UL[N][N], UR[N][N], DL[N][N], DR[N][N], s[N][N];
int n, m, k;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    REP(i, 1, n) REP(j, 1, m) {
        scanf("%lld", &a[i][j]);
        s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j]; // 计算前缀和
    }
    // 计算k*k区域权值
    DEC(i, n, k) DEC(j, m, k) 
        s[i][j] = s[i][j] - s[i-k][j] - s[i][j-k] + s[i-k][j-k];
    //DP计算每个点的四个方位的最大k*k区域
    REP(i, k, n) REP(j, k, m) 
        UL[i][j] = max(s[i][j], max(UL[i-1][j], UL[i][j-1]));
    REP(i, k, n) DEC(j, m - k + 1, 1) 
        UR[i][j] = max(s[i][j+k-1], max(UR[i-1][j], UR[i][j+1]));
    DEC(i, n - k + 1, 1) REP(j, k, m) 
        DL[i][j] = max(s[i+k-1][j], max(DL[i+1][j], DL[i][j-1]));
    DEC(i, n - k + 1, 1) DEC(j, m - k + 1, 1) 
        DR[i][j] = max(s[i+k-1][j+k-1], max(DR[i+1][j], DR[i][j+1]));
    // 分情况讨论：
    // 1.前四种
    ll ans = 0;
    if(2*k <= n && 2*k <= m) // 别忘了限制条件
        REP(i, 1, n) REP(j, 1, m) {
            /*|-| |*/ans = max(ans, UL[i][j] + DL[i+1][j] + UR[n][j+1]);
            /*| |-|*/ans = max(ans, UR[i][j] + DR[i+1][j] + UL[n][j-1]);
            /*|-`-|*/ans = max(ans, UL[i][j] + UR[i][j+1] + DR[i+1][1]);
            /*|-.-|*/ans = max(ans, DL[i][j] + DR[i][j+1] + UR[i-1][1]);
        }
    // 2.后两种
    if (3*k<= n) 
        REP(i, 2 * k, n - k) REP(j, k, m) 
            ans = max(ans, UL[n][j - k] + UR[n][j+1] + s[i][j]);
    if (3*k<= m) 
        REP(i, k, n) REP(j, 2 * k, m - k) 
            ans = max(ans, UL[i - k][m] + DL[i+1][m] + s[i][j]);
    printf("%lld\n", ans);
    return 0;
}