제출 #18032

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

cut

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
 
int dp[51][51];
int dp2[51][51][51][51];
 
int f(int h1, int w1, int h2, int w2){
    if(w2 == 0 || h2 == 0){
        return dp[h1][w1];
    }
    if(~dp2[h1][w1][h2][w2]) return dp2[h1][w1][h2][w2];
    int ret = 1e9;
    for(int j=1; j<h1; j++){
        if(j <= h2){
            ret = min(ret, dp[w1 - w2][j] + f(h1 - j, w1, h2 - j, w2));
        }
        else{
            ret = min(ret, dp[w1][h1 - j] + f(j, w1, h2, w2));
        }
    }
    for(int j=1; j<w1; j++){
        if(j <= w2){
            ret = min(ret, dp[j][h1 - h2] + f(h1, w1 - j, h2, w2 - j));
        }
        else{
            ret = min(ret, dp[w1 - j][h1] + f(h1, j, h2, w2));
        }
    }
    return dp2[h1][w1][h2][w2] = ret;
}
 
int main(){
    memset(dp2,-1,sizeof(dp2));
    int a, b, c, d;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for(int i=1; i<=50; i++){
        for(int j=1; j<=50; j++){
            if(i == j) dp[i][j] = 1;
            else{
                dp[i][j] = 1e9;
                for(int k=1; k<i; k++){
                    dp[i][j] = min(dp[i][j], dp[k][j] + dp[i-k][j]);
                }
                for(int k=1; k<j; k++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j-k]);
                }
            }
        }
    }
    printf("%d",f(a, b, c, d));
}

• Subtask 1: 25 / 25