[UVA 1629] Cake slicing[기억화 검색]
제목 분석: 한 직사각형 케이크에 체리가 여러 개 있는데, 지금 해야 할 일은 가장 적은 거리를 잘라서 직사각형 모양의 작은 케이크를 잘라서 케이크마다 체리가 하나씩 있게 하는 것이다. 최소 절단 거리는?
문제풀이 사고방식: 케이크를 자르는 이상 무한 절단의 과정(귀속?)을 느낄 수 있다.아무튼 그런 느낌 있어.그리고 데이터는 20*20입니다.그럼 기억화 검색해봐.우리는 dp[u][d][l][r]를 u(up)로 이전 d(down)를 하계, l을 왼쪽 경계, r를 오른쪽 경계의 최소 절단 거리로 설정합니다.경계는 앵두 한 조각만 있으면 분명히 자르지 않고 0으로 돌아간다.전체 구역에 체리가 없을 때, 이 구역은 무효 절단으로 무궁무진하게 설정됩니다.
개인적인 느낌: 룸메이트는 폭력적으로 하나하나 절단할 수 있다고 일깨워 주지만 머릿속에는 아무런 느낌도 없다. 귀속할 생각은 하나도 없다. 눈이 멀어 울려고 한다TAT는 마지막에 다른 사람의 것을 보고 밝아진다==
구체적인 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, m, dp[25][25][25][25];
bool has[25][25]; //
int sum(int u, int d, int l, int r) //
{
int ret = 0;
for (int i = u + 1; i <= d; ++i)
for (int j = l + 1; j <= r; ++j)
{
if (has[i][j]) ++ret;
if (ret == 2) return 2; // ，
}
return ret;
}
int dfs(int u, int d, int l, int r)
{
int &ret = dp[u][d][l][r];
if (ret != -1) return ret;
int total = sum(u,d,l,r);
if (total == 1) return ret = 0; // 0，
if (!total) return ret = INF; // ，
ret = INF;
for (int i = u + 1; i < d; ++i) //
ret = min(ret, dfs(u,i,l,r) + dfs(i,d,l,r) + r - l);
for (int i = l + 1; i < r; ++i) //
ret = min(ret, dfs(u,d,l,i) + dfs(u,d,i,r) + d - u);
return ret;
}
int main()
{
int k, x, y, kase = 0;
while(cin >> n >> m >> k)
{
memset(dp, -1, sizeof dp);
memset(has, 0, sizeof has);
for (int i = 0; i < k; ++i) cin >> x >> y, has[x][y] = 1;
cout << "Case " << ++kase << ": " << dfs(0, n, 0, m) << '
';
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
