xtu数据结构 B. Get Many Persimmon Trees
B. Get Many Persimmon Trees
64-bit integer IO format: %lld Java class name: Main
For example, in Figure 1, the entire field is a rectangular grid whose width and height are 10 and 8 respectively. Each asterisk (*) represents a place of a persimmon tree. If the specified width and height of the estate are 4 and 3 respectively, the area surrounded by the solid line contains the most persimmon trees. Similarly, if the estate's width is 6 and its height is 4, the area surrounded by the dashed line has the most, and if the estate's width and height are 3 and 4 respectively, the area surrounded by the dotted line contains the most persimmon trees. Note that the width and height cannot be swapped; the sizes 4 by 3 and 3 by 4 are different, as shown in Figure 1.
Figure 1: Examples of Rectangular Estates
Your task is to find the estate of a given size (width and height) that contains the largest number of persimmon trees.
Input
N
W H
x1 y1
x2 y2
...
xN yN
S T
N is the number of persimmon trees, which is a positive integer less than 500. W and H are the width and the height of the entire field respectively. You can assume that both W and H are positive integers whose values are less than 100. For each i (1 <= i <= N), xi and yi are coordinates of the i-th persimmon tree in the grid. Note that the origin of each coordinate is 1. You can assume that 1 <= xi <= W and 1 <= yi <= H, and no two trees have the same positions. But you should not assume that the persimmon trees are sorted in some order according to their positions. Lastly, S and T are positive integers of the width and height respectively of the estate given by the lord. You can also assume that 1 <= S <= W and 1 <= T <= H.
The end of the input is indicated by a line that solely contains a zero.
Output
Sample Input
16
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0
Sample Output
4
3 解题:题目比较长啊。。。开始没高清意思。。。鸟语太挫了。。。给出平面上n个点,最后要在这个平面内找出一个举行内部点数最多的指定长宽的矩形,输出最多包括的点数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#define LL long long
#define INF 0x3f3f3f
using namespace std;
const int maxn = ;
int tree[maxn][maxn];
int lowbit(int x) {
return x&(-x);
}
void update(int x,int y,int val) {
for(int i = x; i < maxn; i += lowbit(i)) {
for(int j = y; j < maxn; j += lowbit(j)) {
tree[i][j] += val;
}
}
}
int sum(int x,int y) {
int ans = ;
for(int i = x; i; i -= lowbit(i)) {
for(int j = y; j; j -= lowbit(j)) {
ans += tree[i][j];
}
}
return ans;
}
int main() {
int n,w,h,x,y;
while(scanf("%d",&n),n) {
scanf("%d%d",&w,&h);
memset(tree,,sizeof(tree));
for(int i = ; i < n; i++) {
scanf("%d%d",&x,&y);
update(x,y,);
}
scanf("%d%d",&x,&y);
int ans = ,temp;
for(int i = x; i <= w; i++) {
for(int j = y; j <= h; j++) {
temp = sum(i,j) - sum(i-x,j) - sum(i,j-y) + sum(i-x,j-y);
if(temp > ans) ans = temp;
}
}
printf("%d\n",ans);
}
return ;
}
最新文章
- Linux开机自动登录(文本模式)
- python之import子目录文件
- PDF 补丁丁 0.5.0.2078 测试版发布:不用打字,也能加书签
- 王爽<;汇编语言>;实验十
- 使用OpenLDAP构建基础账号系统
- FileIputeStream用于读写文件,并且用字节的方式表示出来
- 李洪强-C语言6-控制结构
- 【linux】/etc/passwd文件
- android API文档查询---context、toast、SharedPreferences
- JavaScript学习总结【3】、JS对象
- WordPress BuddyPress Extended Friendship Request插件跨站脚本漏洞
- js简易猜数字
- CF1044B Intersecting Subtrees 构造+树论
- AngularJs $scope 里面的$apply 方法和$watch方法
- jquery 常用获取值得方法汇总
- PHP获取网页内容的几种方法
- 有道单词导入 有道单词 生词本 批量导入 添加 有道单词XML 背单词
- canvas二进制字符下落
- 绘图和数据可视化工具包——matplotlib
- 推荐一款很好用的调试js的eclipse插件
热门文章
- phpmyadmin 出现Table &#39;root.pma_table_uiprefs&#39; doesn&#39;t exist
- 【转】常用邮箱的 IMAP/POP3/SMTP 设置
- 在Window上用cmd创建.htaccess文件
- Magento 0元订单 支付方式 -- Magento 0 Subtotal Payment Method
- GetClassName 取得的类名有
- ASP.NET MVC执行流程图
- COGS 930. [河南省队2012] 找第k小的数
- vijos 1190 繁忙的都市
- codevs 1992 聚会
- WPF知识点全攻略05- XAML内容控件