奥林匹克竞赛论文-《浅谈用极大化思想解决最大子矩形问题》附件整理版.doc

PAGE PAGE 4 一些例题的原题 1、奶牛浴场 奶牛浴场 【问题描述】 由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？ John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。 Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。 【输入文件】 输入文件的第一行包含两个整数L和W，分别表示牛场的长和宽。文件的第二行包含一个整数n，表示产奶点的数量。以下n行每行包含两个整数x和y，表示一个产奶点的坐标。所有产奶点都位于牛场内，即：0xL，0yW。 【输出文件】 输出文件仅一行，包含一个整数S，表示浴场的最大面积。 【输入输出样例】 happy.in happy.out 10 10 4 1 1 9 1 1 9 9 9 80 【参数约定】 0n5000 1L,W30000 2、Candy 糖果盒 ( Candy Box ) 问题描述： 一个被分为 n*m　个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。 任　务　： 请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果。 输入格式： 从文件CANDY.INP读入数据。第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i ][ j ]，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中： 1 ≤ n，m ≤ 1000 0 ≤ a [ i ][ j ]≤ 255 注意：本题提供 16 MB 内存，时间限制为2秒。 输出格式： 输出最大糖果数到 CANDY.OUT。 样例 CANDY.INP CANDY.OUT 3 4 1 2 3 4 5 0 6 3 10 3 4 0 17 注： 10 3 4 这个矩形的糖果数最大 3、Big Barn Big Barn A Special Treat Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis. EXAMPLE Consider the following grid of Farmer Johns land where `. represents a parcel with no trees and `# represents a parcel with trees: 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # . . . # . . 3 . . . . . . . . 4 . . . . . . . . 5 . . . . . . . . 6 .