本文主要是介绍uva 11782 - Optimal Cut(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 11782 - Optimal Cut
题目大意：按照前序给出一棵完全树的前序，每个节点的值，现在要求在这棵树上切最多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\n", solve());}return 0;
}
这篇关于uva 11782 - Optimal Cut(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
