BZOJ 1127 - [POI2008]KUP | Sengxian's Blog

BZOJ 1127 - [POI2008]KUP

#动态规划 #思维 #悬线法动态规划

Published on 2016-09-28

描述

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

分析

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

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

考虑二维的情况，我们猜测类似的引理：

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

所以问题就变为了找到一个元素 $< k$ 且和 $\ge 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;
}

BZOJ 1135 - [POI2009]Lyz BZOJ 1126 - [POI2008]Uci