Wx::

2018 acm 河南省赛题 - i

本文又进行了一次小更新;

题目:

详情:-brev-

I. Image Recognition Time Limit: 6000MS
The monitoring system without any person does not necessarily require a large number of dynamic images. It is enough to transport an immobile image in ** seconds in most practical condition.

In the JD-T warehouse, the goods is stored in large cubical crates, all of which have the same dimensions. The crates are stacked in neat piles, forming a three-dimensional grid. The remote online monitoring system takes pictures of the piles once in S seconds using three cameras: a front camera, a side camera and a top camera. The image from the front camera shows the height of the tallest pile in each column, the image from the side camera shows the height of the tallest pile in each row, and the image from the top camera shows whether or not each pile is empty. If the monitoring system detects a change in any of the images, it sounds an alarm.

0 3 4 5
1 3 1 4

(Figure I-1)(请忽略表格中粗细差别)

0 1 1 5
1 3 4 1

(Figure I-2)

0 1 2 5
1 3 4 3

(Figure I-3)

Figure I-2 , I-3 and figure I-1 have the same images from each of the cameras.

A theft gang noticed this unmanned warehouse. They found that it took T seconds to transport a crate. They wants to steal as many crates as possible. Since they cannot disable the monitoring system, they plans to fool it by arranging the remaining crates into piles so that the next set of camera images are the same.

Is the remote online monitoring system safe? If it's not safe, the maximum number of crates that can be stolen while leaving a configuration of crates that will fool the monitoring system, camera images remain unchanged.

  • Input
    The first line of the input contains one integer T, which is the number of test cases (1<=T<=6). Each test case specifies:

    • Line 1: S T
      (1<=S=1012 1<=T=103 )
    • Line 2: m n
      rows and columns in the grid, respectively. (1<=m, n<=100)
    • Line 3..m+3: each line contains n integers, the heights (in crates) of the piles in the corresponding row.
      (all heights are between 0 and 109 inclusive.)
  • Output
    For each test case , print the maximum number of crates that can be stolen without being detected.

over


思路:

简单的二重循环并不可靠,因为存在多行最高值可分配至多列充当最高值的判优情况,且在行列最高值交点处可能为 0(无法放置箱子)

  • 二分匹配

  • 数学公式推导

  • 回溯,内存消耗较大且可能不适用于超大规模(如 100*100)的数据

  • 此处采用回溯


代码:

#include <iostream>

using namespace std;

const int N = 101;
long long T, all, one, row, col;  // 样例数,总时间,移一个箱子时间,行数,列数

long long crates[N][N];  // 原始数据
long long rowM[N]; // 每行中最高
long long colM[N];  // 每列中最高
int rowPos[N]; // 对于 rowM 中的每个元素的放于第几列
bool colFinish[N]; // 该列是否已有最高值

int likePos[N][N]; // rowM 中每个元素可以放在哪些可能的列(高度与其相等),用于回溯

int rowMPosTemp[N]; // 用于回溯中暂时记录某行最高值放于哪列
int rowMPosMax[N]; // 用于回溯中记录每行最高值放于哪列
int rowMPutMax; // 行最高值放于列的最大行数
int rowMPutTemp; // 暂存

// 回溯,将每行的最高值最优分配到哪列,以最省箱子数:
void back(int t) {
    if (t == row) { // 最后一行处理结束:
        if (rowMPutTemp > rowMPutMax) {
            rowMPutMax = rowMPutTemp;
            for (int i = 0; i < row; i++) {
                rowMPosMax[i] = rowMPosTemp[i];
            }
        }
        return;
    }

    bool flag = false;
    for (int j = 0; j < col; j++) {
        if (likePos[t][j] == 1 && colFinish[j] == false && crates[t][j] != 0) {
            // 如果第 t 行最大值可放在第 j 列充当最高值 且 第 j 列还未被填最大值:
            flag = true; // 说明该行可放置于某列充当最高值
            rowMPutTemp++; // 可充当列最高值的行数加 1
            rowMPosTemp[t] = j;
            colFinish[j] = true;
            back(t + 1);
            colFinish[j] = false;
            rowMPosTemp[t] = -1;
            rowMPutTemp--;
        }
    }
    if (!flag) { // 第 t 行最高值无法充当某列最高值
        for (int j = 0; j < col; j++) {
            if (rowM[t] == 0) { // 单独判断最高值为 0,即整行都为 0 的情况
                rowMPosTemp[t] = 0;
                back(t + 1);
                rowMPosTemp[t] = -1;
                break;
            }
            if (rowM[t] <= colM[j] && crates[t][j] != 0) {
                // 一定要注意不等于 0
                // 此时只需找一列,此列最高值大于第 t 行最高值即可放:
                rowMPosTemp[t] = j;
                back(t + 1);
                rowMPosTemp[t] = -1;
            }
        }
    }
}

int main() {
    cin >> T;
    long long temp; // 暂存每行或每列最高值
    long long sum; // 完成三视图需要的箱子
    long long unBlank; // 非空白数
    long long old = 0; // 初始箱子数
    for (long long z = 0; z < T; z++) {
        sum = 0;
        unBlank = 0;
        old = 0;
        cin >> all >> one;
        cin >> row >> col;

        // 读数据:
        for (int i = 0; i < row; i++) {
            temp = 0;
            for (int j = 0; j < col; j++) {
                cin >> crates[i][j];
                if (crates[i][j] > temp) {
                    temp = crates[i][j];
                }
                if (crates[i][j]) {
                    unBlank++;
                    old += crates[i][j];
                }

                likePos[i][j] = -1; // 顺便初始化
            }
            rowM[i] = temp; // 记录每行最高值
            sum += temp; // 所需箱子加上每行最高值

            rowPos[i] = -1; // 顺便初始化
        }

        // 初始化每列最高值:
        for (int j = 0; j < col; j++) {
            temp = 0;
            for (int i = 0; i < row; i++) {
                if (crates[i][j] > temp) {
                    temp = crates[i][j];
                }
            }
            colM[j] = temp;

            colFinish[j] = false; // 顺便初始化
        }

        // 判断每行最高是否存在与其相等的每列最高(该行列共用这一堆箱子):
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (rowM[i] == colM[j] && crates[i][j] != 0) {
                    likePos[i][j] = 1; // 第 i 行最高值可能同时充当第 i 列最高值
                }
            }
        }

        // 对于行列共用最高值的情况,采取最佳分配(回溯),使得最高值被共用最多:
        rowMPutMax = 0;
        rowMPutTemp = 0;
        back(0); // 从第 0 行开始回溯,以把尽可能多的行最高值充当列最高值

                 // 对于分配到最高值的列,colFinish 改为 true(因为之前回溯会把部分 colFinish 值冲掉):
        if (rowMPutMax > 0) {
            for (int i = 0; i < row; i++) {
                colFinish[rowMPosMax[i]] = true;
                if (rowM[i]!=0) {
                    unBlank --; // 当行最高值不为 0 时,它已被放入到某列,所以非空白数减 1
                }
            }
        }

        // 最后把还没有最高值的列分配一下(单独增加箱子):
        for (int j = 0; j < col; j++) {
            if (colFinish[j] == false && colM[j] != 0) {
                sum += colM[j];
                unBlank--;
            }
        }

        // 总结数据:
        sum += unBlank; // 加上非空白数,每个非空白数需要放 1 个箱子(俯视图达标)
        sum = old - sum; // 原有的减去需要的就是可偷的
        if (sum > all / one) { // 判断时间够不够
            sum = all / one;
        }

        cout << sum << endl;
    }

    return 0;
}

样例:

3 组官方样例,5 组自造数据

Sample Input Sample Output
8

10000 100
5 5
1 4 0 5 2
2 1 2 0 1
0 2 3 4 4
0 3 0 3 1
1 2 2 1 1

10000 100
2 3
50 20 3
20 10 3

1000 99
2 3
50 20 3
20 10 3

3700 100
5 5
8 7 1 0 4
5 3 6 0 1
1 1 2 4 4
0 7 6 5 3
2 6 4 3 7

6500 100
4 3
50 20 3
20 10 3
50 3 20
20 3 10

55 1
4 3
50 19 3
19 10 3
50 3 20
20 3 10

7 1
3 4
2 2 4 1
4 0 5 4
1 3 4 0

8 1
3 4
2 2 4 1
4 0 5 4
1 3 4 0
9
30
10
37
64
55
7
8

More

  • 任何建议及问题均可联系我
  • 更多可关注:wangxw.cn
336

评论(0

评论 取消
验证码:
搜索