Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

部分和+暴力0ms 1A就是high啊

Posted by 13091258 at 2012-07-19 16:35:05 on Problem 2029
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator