게이지
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20 + 5;
const int INF = 0x3f3f3f3f;
#define REP(i,j,n) for(int i=(j);i<=(n);i++)
int n, m, k, inp[maxn][maxn], cnt[maxn][maxn], kase, dp[maxn][maxn][maxn][maxn], a, b;
int DP(int i, int j, int k, int l)
{
int &res = dp[i][j][k][l];
if (res != 0) return res;
int cherry = cnt[k][l] - cnt[i - 1][l] - cnt[k][j - 1] + cnt[i - 1][j - 1];
if (cherry == 0) return INF;
if (cherry == 1) return 0;
res = INF;
REP(a, i, k) res = min(res, DP(i, j, a, l) + DP(a + 1, j, k, l) + l - j + 1);
REP(b, j, l) res = min(res, DP(i, j, k, b) + DP(i, b + 1, k, l) + k - i + 1);
return res;
}
int main(int argc, char const *argv[])
{
while (cin >> n >> m >> k)
{
memset(cnt, 0, sizeof(cnt));
memset(dp, 0, sizeof(dp));
memset(inp, 0, sizeof(inp));
while (k--) cin >> a >> b, inp[a][b] = 1;
REP(i, 1, n) REP(j, 1, m) cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + inp[i][j];
cout << "Case " << ++kase << ": " << DP(1, 1, n, m) << endl;
}
return 0;
}제목 자체가 어렵지 않은데, 체리 개수를 집계하는 방법을 생각해 내지 못했다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
