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