제출 #544663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544663		pokmui9909	L 모양의 종이 자르기 (KOI15_cut)	C++17	25 / 25	304 ms	20072 KiB

cut

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
ll D[55][55];
ll D2[55][55][55][55];
 
ll dfs(ll n, ll m)
{
    if(n < m) swap(n, m);
    if(n == m) return 1;
    if(D[n][m]) return D[n][m];
    if(n >= 3 * m) return dfs(n - m, m) + 1;
 
    ll ans = 1e15;
    for(int i = 1; i <= n - 1; i++) ans = min(ans, dfs(i, m) + dfs(n - i, m));
    for(int i = 1; i <= m - 1; i++) ans = min(ans, dfs(n, i) + dfs(n, m - i));
 
    return D[n][m] = ans;
}
 
ll dfs2(ll x1, ll y1, ll x2, ll y2)
{
    if(x2 == 0 || y2 == 0) return dfs(x1, y1);
    if(D2[x1][y1][x2][y2]) return D2[x1][y1][x2][y2];
 
    ll ans = 1e15;
 
    for(int i = 1; i <= y1 - y2 - 1; i++) ans = min(ans, dfs(x1, i) + dfs2(x1, y1 - i, x2, y2));
    for(int i = 1; i <= x1 - x2 - 1; i++) ans = min(ans, dfs(y1, i) + dfs2(x1 - i, y1, x2, y2));
    for(int i = y1 - y2 + 1; i < y1; i++) ans = min(ans, dfs(x1 - x2, y1 - i) + dfs2(x1, i, x2, i - (y1 - y2)));
    for(int i = x1 - x2 + 1; i < x1; i++) ans = min(ans, dfs(y1 - y2, x1 - i) + dfs2(i, y1, i - (x1 - x2), y2));
    ans = min(ans, dfs(x1 - x2, y1) + dfs(y1 - y2, x2));
    ans = min(ans, dfs(x1, y1 - y2) + dfs(x1 - x2, y2));
 
    return D2[x1][y1][x2][y2] = ans;
}
 
int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
 
    ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    cout << dfs2(x1, y1, x2, y2);
}

• Subtask 1: 25 / 25