BZOJ 1127 - [POI2008]KUP

Published on 2016-09-28

题目地址

描述

给一个 n×n(n2000)n\times n(n\le 2000) 的地图,每个格子有一个价格,找一个矩形区域,使其价格总和位于 [k,2k][k, 2k]

分析

按照通常的思维方法,我们先考虑一维的情况。显然如果存在一个 [k,2k][k, 2k] 价值的点,那么直接输出即可;如果存在 2k\ge 2k 的点,那么这个点是废点,所以这就得出一个引理:

引理一:如果一段序列中的数 <k< k,且它们的和 k\ge k,那么一定存在一个连续的子序列,使得子序列的和在 [k,2k][k, 2k] 之间。
证明:只需要考虑和 >2k> 2k 的情况,我们删掉最后一个数,由于所有的数都 <k< k,剩下的数的和要么还是 >2k> 2k,这种情况接着删下去;要么跑到 [k,2k][k, 2k] 之间,这种情况已经得到解。

考虑二维的情况,我们猜测类似的引理:

引理二:如果一个矩阵中的数 <k< k,且它们的和 k\ge k,那么一定存在一个子矩阵,使得子矩阵的和在 [k,2k][k, 2k] 之间。
证明:如果矩阵只有一行,这就是引理一。否则有多行,设矩阵的和为 SS,那么只考虑 S>2kS > 2 k 的情况,考虑矩阵的第一行和最后一行,它们之中必有一行的和 S2\le \frac S 2,删掉较小的一行,要么和仍然 >2k> 2k,接着删即可;要么和跑进 [k,2k][k, 2k],这种情况已经得到解。

所以问题就变为了找到一个元素 <k< k 且和 k\ge k 的子矩阵,只需要将 >2k> 2k 看做障碍点(没有 [k,2k][k, 2k] 的点,如果有直接输出答案),做一次最大子矩阵即可,用悬线法 DP 就可求解。

代码

//  Created by Sengxian on 2016/9/26.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1127 悬线法动态规划
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 2000 + 3;
int n, k, a[MAX_N][MAX_N];
bool block[MAX_N][MAX_N];
int up[MAX_N][MAX_N], le[MAX_N][MAX_N], ri[MAX_N][MAX_N];
ll d[MAX_N][MAX_N];

inline ll sum(int x1, int y1, int x2, int y2) {
    return d[x2][y2] - d[x2][y1] - d[x1][y2] + d[x1][y1];
}

void print(int x1, int y1, int x2, int y2) {
    ll s = sum(x1, y1, x2, y2);
    if (s <= 2 * k) return printf("%d %d %d %d\n", y1 + 1, x1 + 1, y2, x2), void();
    if (x2 - x1 == 1) {
        while (s > 2 * k) s -= a[x1][y1++];
        printf("%d %d %d %d\n", y1 + 1, x1 + 1, y2, x2);
    } else if (sum(x1, y1, x1 + 1, y2) <= s >> 1)
        print(x1 + 1, y1, x2, y2);
    else print(x1, y1, x2 - 1, y2);
}

bool judge() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (block[i][j]) up[i][j] = 0, le[i][j] = 0, ri[i][j] = n;
            else up[i][j] = i == 0 ? 1 : up[i - 1][j] + 1;
        }
        int last = -1;
        for (int j = 0; j < n; ++j) {
            if (block[i][j]) last = j;
            else le[i][j] = i == 0 ? last + 1 : max(le[i - 1][j], last + 1);
        }
        last = n;
        for (int j = n - 1; j >= 0; --j) {
            if (block[i][j]) last = j;
            else ri[i][j] = i == 0 ? last - 1 : min(ri[i - 1][j], last - 1);
        }
        for (int j = 0; j < n; ++j) if (!block[i][j]) {
            if (sum(i - up[i][j] + 1, le[i][j], i + 1, ri[i][j] + 1) >= k) {
                print(i - up[i][j] + 1, le[i][j], i + 1, ri[i][j] + 1);
                return true;
            }
        }
    }
    return false;
}

int main() {
    k = ReadInt(), n = ReadInt();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            a[i][j] = ReadInt();
            d[i + 1][j + 1] = a[i][j] + d[i + 1][j] + d[i][j + 1] - d[i][j];
            if (a[i][j] >= k && a[i][j] <= 2 * k) {
                return printf("%d %d %d %d\n", j + 1, i + 1, j + 1, i + 1), 0;
            } else if (a[i][j] > 2 * k) block[i][j] = true;
        }
    if (!judge()) puts("NIE");
    return 0;
}