Submission #18057

#	Time	Username	Problem	Language	Result	Execution time	Memory
18057		chan492811	L 모양의 종이 자르기 (KOI15_cut)	C++98	25 / 25	336 ms	27520 KiB

cut

#include <cstdio>
#include <cstring>
#include <algorithm>
#define n 50
#define INF 1000000000
using namespace std;
int l_paper[51][51][51][51],rec[51][51];
int h1,w1,h2,w2;
int main(){
    int i,j,k,l,p;
    scanf("%d %d %d %d",&h1,&w1,&h2,&w2);
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            rec[i][j]=INF;
            if(i==1 || j==1){ rec[i][j]=max(i,j); continue; }
            if(i==j){ rec[i][j]=1; continue; }
            for(k=1;k<i;k++) rec[i][j]=min(rec[i][j],rec[k][j]+rec[i-k][j]);
            for(k=1;k<j;k++) rec[i][j]=min(rec[i][j],rec[i][k]+rec[i][j-k]);
        }
    }
    for(i=1;i<=h1;i++){
        for(j=1;j<=w1;j++){
            for(k=1;k<i;k++){
                for(l=1;l<j;l++){
                    l_paper[i][j][k][l]=INF;
                    l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[k][j-l]+rec[i-k][j]);
                    l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[i-k][l]+rec[i][j-l]);
                    for(p=1;p<j-l;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][i]+l_paper[i][j-p][k][l]);
                    for(p=1;p<l;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][i-k]+l_paper[i][j-p][k][l-p]);
                    for(p=1;p<k;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][j-l]+l_paper[i-p][j][k-p][l]);
                    for(p=1;p<i-k;p++) l_paper[i][j][k][l]=min(l_paper[i][j][k][l],rec[p][j]+l_paper[i-p][j][k][l]);
                }
            }
        }
    }printf("%d",l_paper[h1][w1][h2][w2]);
    return 0;
}

• Subtask 1: 25 / 25