uva 11782 - Optimal Cut(dp)
제목의 대의: 앞의 순서에 따라 완전한 나무의 앞의 순서를 제시하고 각 노드의 값을 제시한다. 지금은 이 나무에 가장 많은 k칼을 썰어야 얻는 값이 가장 크다. 그러나 한 가지 요구가 있다. 바로 모든 자수에 대해 가장 많은 칼을 썰고 각 잎의 노드를 잘라야 한다는 것이다.
문제풀이 사고방식: dp[i][k]는 i 노드가 뿌리인 자수를 나타내고 k칼을 자른 후의 최대치를 나타낸다.각 노드마다 왼쪽 아이와 오른쪽 아이의 구분이 있는데 한 상태 dp[i][k]에 대해 왼쪽 아이의 칼 수 t, dp[i][k]=max(dp[i][k], dp[i*2+1][t]+dp[i*2+2][k-t])를 매거한다.또한 dp[i][k]는 dp[i][k-1]에서 얻을 수 있으니 k칼보다 작게 자르면 된다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = (1<<20)+5;
const int K = 25;
const int INF = 0x3f3f3f3f;
int n, k, dp[N][K];
void buildTree(int u, int d) {
if (d > n)
return;
scanf("%d", &dp[u][1]);
buildTree(u*2+1, d+1);
buildTree(u*2+2, d+1);
}
int solve () {
int t = (1<<(n+1))-2;
for (int i = 2; i <= k; i++) {
for (int j = t; j >= 0; j--) {
int p = j*2+1;
int q = j*2+2;
dp[j][i] = dp[j][i-1];
if (p > t || q > t)
continue;
for (int x = 1; x < i; x++)
dp[j][i] = max(dp[j][i], dp[p][x] + dp[q][i-x]);
}
}
return dp[0][k];
}
int main () {
while (scanf("%d", &n) == 1 && n != -1) {
scanf("%d", &k);
buildTree(0, 0);
printf("%d
", solve());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
