글 읽기 - IOI 정원 문제 질문 있어요

bluefire 6년 전 0

안녕하세요 정원 문제에서 질문이 있어서 왔습니다.

직사각형 내부에 있는 장미의 개수가 k개가 되도록 직사각형을 2개 선택해야 하는데,

두 직사각형은 서로 겹치는 영역이 없어야 하고, 두 직사각형 둘레의 합이 최소가 되게 2 직사각형을 선택해야 합니다.

제가 생각하는 솔루션은 장미 i와 장미 j를 선택을 해서 장미 i와 장미 j가 있는 위치를 덮는 직사각형을 그렸을 때

영역내부에 있는 장미가 k개가 된다면 해당 직사각형은 유효한 직사각형이라고 생각을 했고 가장 최적이라 생각을 해서

최대 n^2 개의 직사각형만을 그립니다.

그렇다면 한 직사각형의 왼쪽부분에 위치한 직사각형중에서 최소의 둘레를 구하고 마찬가지로 오른쪽 위쪽 아래쪽 이렇게 선택을 합니다.

그렇게 해서 최소의 둘레 합을 구하려고 하는데 틀리네요 왜 틀릴까요?? ㅠㅠ

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define mm(x) memset(x,0x48,sizeof(x));
#define forn(i,st,ed) for(i=st;i<ed;++i)
#define form(i,st,ed) for(i=st;i>=ed;--i)


const int N = 5005,M = 300;

int AR[M][M];

pair<int,int> point[N];

int get(int x,int y){       //장미 x와 장미 y의 위치를 덮는 직사각형 내부의 장미개수를 구하는 함수

    int x1= point[x].second,x2= point[y].second;

    int y1= point[x].first,y2= point[y].first;

    if(x1>x2)swap(x1,x2);
    if(y1>y2)swap(y1,y2);

    int tot = AR[y2][x2];
    tot-= AR[y1-1][x2];
    tot-= AR[y2][x1-1];
    tot+= AR[y1-1][x1-1];


   
    return tot;
}

struct rec{        //사각형 구조
    int x1,x2,y1,y2;


    rec(){}
    rec(int a,int b,int c,int d):x1(b),x2(d),y1(a),y2(c){
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
    }
    int dule(){        //둘레를 구하는 함수 ㅋㅋ
        return 2*( x2-x1+1 + y2-y1+1);
    }
};

vector<rec> valid;    //유효한 사각형들을 저장해놓는다.
int L[M],R[M],U[M],D[M];//왼쪽 ,오른쪽 , 아래쪽 , 위쪽에 위치한 사각형중 최소의 둘레를 미리 구해놓는다.

int MAXI;

void solve(){
    mm(L);mm(R) ;mm(U) ;mm(D);
    memset(AR,0,sizeof(AR));

    MAXI= L[0];

    int k,l,w,i,j,n,x,y,a,b;
    cin>>l>>w>>n>>k;

    forn(i,0,n)cin>>y>>x,++AR[y][x],point[i].first= y,point[i].second= x;

    forn(i,1,M)
        forn(j,1,M){        //1,1에서부터 i,j까지의 사각형을 그렸을 때, 내부에 존재하는 장미개수
            AR[i][j]= AR[i][j-1] + AR[i-1][j] - AR[i-1][j-1] + AR[i][j];
        }
    
    assert(AR[l][w]==n);
    
    forn(i,0,n)
        forn(j,0,n)
        if(get(i,j)==k){
            valid.push_back(rec(point[i].first,point[i].second,point[j].first,point[j].second));
        }
    
    rec temp;
    
    int dule,mini;
    
    forn(i,0,valid.size()){
        temp = valid[i];
        dule = temp.dule();
        L[temp.x2]= min(L[temp.x2],dule);
        R[temp.x1]= min(R[temp.x1],dule);
        D[temp.y2]= min(dule,D[temp.y2]);
        U[temp.y1]= min(U[temp.y1],dule);
    }
    
    forn(i,1,M)L[i]= min(L[i-1],L[i]), D[i]= min(D[i-1],D[i]);
    
    form(i,M-2,0)R[i]= min(R[i+1],R[i]), U[i]= min(U[i+1],U[i]);
    
    int ret= MAXI;
    
    forn(i,0,valid.size()){
        mini = MAXI;
        temp = valid[i];
    
        mini = min(mini, L[temp.x1-1]);
        mini = min(mini, R[temp.x2+1]);
        mini = min(mini, D[temp.y1-1]);
        mini = min(mini, U[temp.y2+1]);
        
        ret= min(ret, mini +temp.dule()); 
    }
    
    if(ret==MAXI){
        printf("NO\n");return;
    }
    printf("%d\n",ret);
}   

int main(){
    solve();
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

IOI 정원 문제 질문 있어요

bluefire 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말