제출 #18862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18862		Namnamseo	L 모양의 종이 자르기 (KOI15_cut)	C++14	25 / 25	232 ms	34128 KiB

cut

#include <cstdio>

int rectdp[51][51];
bool rectc[51][51];

int min(int a,int b){ return a>b?b:a; }

int rect(int w,int h){
    if(w==h) return 1;
    if(rectc[w][h]) return rectdp[w][h];
    rectc[w][h]=1;
    int& ret=rectdp[w][h];
    ret=1e9;
    int i;
    for(i=1; i<w; ++i) ret=min(ret, rect(i,h)+rect(w-i,h));
    for(i=1; i<h; ++i) ret=min(ret, rect(w,i)+rect(w,h-i));
    return ret;
}

bool chk[51][51][51][51];
int   dp[51][51][51][51];

int work(int a,int b,int c,int d){
    if(a==c) {
        if(b==d) return 1;
        else return rect(a, b-d);
    } else if(b==d){
        return rect(a-c,b);
    } else {
        int& ret=dp[a][b][c][d];
        if(chk[a][b][c][d]) return ret;
        chk[a][b][c][d]=1;
        ret=2e9;
        int i;
        for(i=1; i<=a-c; ++i) ret=min(ret, rect(i,b)+work(a-i,b,c,d));
        for(i=1; i<=b-d; ++i) ret=min(ret, rect(a,i)+work(a,b-i,c,d));
        for(i=1; i<c  ; ++i) ret=min(ret, rect(i,b-d)+work(a-i,b,c-i,d));
        for(i=1; i<d  ; ++i) ret=min(ret, rect(i,a-c)+work(a,b-i,c,d-i));
        return ret;
    }
}

int main()
{
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    printf("%d\n",work(a,b,c,d));
    return 0;
}

• Subtask 1: 25 / 25