| 题目名称 | 1289. [ZJOI 2011] 礼物 |
|---|---|
| 输入输出 | gift.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 20 |
| 题目来源 |
 Makazeu
于2013-01-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：11， 提交：43， 通过率：25.58% | ||||
 SBBBBBB |
100 | 1.704 s | 57.11 MiB | C++ |
 Link |
100 | 2.400 s | 33.88 MiB | C++ |
 fleey |
100 | 4.025 s | 42.94 MiB | C++ |
 四季木哥 |
100 | 4.176 s | 21.55 MiB | C++ |
 shy |
100 | 4.412 s | 26.96 MiB | Pascal |
|
shy |
100 | 4.534 s | 26.96 MiB | Pascal |
|
shy |
100 | 4.573 s | 25.61 MiB | Pascal |
|
shy |
100 | 4.842 s | 48.31 MiB | Pascal |
 cstdio |
100 | 5.086 s | 74.52 MiB | C++ |
 ww944606393 |
100 | 5.137 s | 78.44 MiB | C++ |
| 关于 礼物 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
犇。。。
但犇你的程序为何总是10000000行、、、、o_o 哎。。没有神犇的题解的话。。这题我能写出来么、、、、哦，对还要在规定时间内。。。o_o  GDFRWMY
2014-04-20 11:42
2楼
| ||||
|
WTF我居然连单调队列都不会写了……
| ||||
【题目描述】
小白的生日就要到了，小蓝决定送一件自己亲手做的手工艺品使自己的礼物与众不同。具体来说，小蓝已经通过某种方式制作出了一个p×q×r的木块（由pqr个单位小木块组成）。但由于小蓝手艺不精，现在这个木块中的有些单位小木块是有问题的(有裂缝、里面是空心等等)，这样的礼物小蓝是不可能直接送出去的。
于是小蓝决定在这个木块中再挖出一个a×a×b的子木块(即要求挖出的长方体木块存在两条长度相等的相邻边)，当然这个子木块中是不能包含有问题的单位小木块的。为了使这个木块上能包含更多的图案，小蓝希望从所有可行的方案中挑取4ab的值最大的方案。但小蓝光检测木块中哪些地方有问题就已经耗尽了体力，作为小蓝的好友，你能帮帮小蓝吗？
【输入格式】
每个输入文件中仅包含一个测试数据。
第一行包含三个由空格隔开的正整数，p,q,r。
接下来有pq行，每行包含r个字符，每个字符只可能是’P’(Poor)或者’N’(Nice)，表示该单位小木块有问题或者没问题。具体的说，第1+(yp+x-p)行的第z个字符描述的是坐标为(x,y,z)的小木块情况。(1<=x<=p,1<=y<=q,1<=z<=r)
【输出格式】
输出文件仅包含一个整数，表示最佳方案的4ab的值。
【样例输入】
3 2 5
PNNNN
PNNNN
NPPNP
PNNNP
NNNNP
PPNNP
【样例输出】
24
【提示】
对于100%的数据，0<p,q,r<=150，输入中至少包含一个’N’
【来源】
ZJOI2011 Day1