首页 > 代码库 > uva 10304 - Optimal Binary Search Tree 区间dp
uva 10304 - Optimal Binary Search Tree 区间dp
题目链接
给n个数， 这n个数的值是从小到大的， 给出个n个数的出现次数。 然后用他们组成一个bst。访问每一个数的代价是这个点的深度*这个点访问的次数。 问你代价最小值是多少。
区间dp的时候， 如果l >= r， 那么返回0， l == r-1， 返回两个数中小的一个。 其他情况的话枚举分界点进行状态转移。
#include <bits/stdc++.h>using namespace std;#define mem1(a) memset(a, -1, sizeof(a))const int inf = 1061109567;int dp[260][260], a[260], pre[260];int dfs(int l, int r){ if(~dp[l][r]) return dp[l][r]; if(l >= r) return dp[l][r] = 0; if(l == r - 1) { return dp[l][r] = min(a[l], a[r]); } dp[l][r] = inf; for(int i = l-1; i < r; i++) { dp[l][r] = min(dp[l][r], dfs(l, i) + dfs(i + 2, r) + pre[r]-pre[l-1] - a[i+1]); } return dp[l][r];}int main(){ int n; while(~scanf("%d", &n)) { mem1(dp); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); pre[i] = pre[i-1] + a[i]; } printf("%d\n", dfs(1, n)); } return 0;}
uva 10304 - Optimal Binary Search Tree 区间dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。