| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
部分和+暴力0ms 1A就是high啊#include<iostream>
#include<string>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define swap(a,b) {int t=a; a=b; b=t;}
using namespace std;
int n,w,h,s,t;
int a[101][101];//有为1 否则为0
int b[101][101];
//部分和
void proc(){//预先处理 求出以1,1为左上的所有矩阵和
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++)
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
}
int get(int x1,int y1,int x2,int y2){//经过proc后 可常数时间得到任意矩阵和
return b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1];
}
void dp(){
int Max=0;
//下面就是枚举矩形 找到最大的 暴力啊
for(int i=1;i<=h;i++){
int x=i+t-1;
if(x>h) break;
for(int j=1;j<=w;j++){
int y=j+s-1;
if(y>w) break;
Max=max(Max,get(i,j,x,y));
}
}
cout<<Max<<endl;
}
void init(){
while(cin>>n && n!=0){
cin>>w>>h;
int i,j;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
while(n--){
cin>>j>>i;
a[i][j]=1;
}
cin>>s>>t;
proc();
dp();
}
}
int main(){
init();
system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator