首页 > 代码库 > Vijos p1518河流 树形DP
Vijos p1518河流 树形DP
https://vijos.org/p/1518
这题代码我基本是抄的,实在太难想了。但是也学到了一些东西。
比如:多叉树转二叉树存,这个细细一想,确实使得在dfs的时候,实现起来方便很多。
说一说具体 dfs的思路,思路和网上那个一模一样的,我刚学树形dp,可能上网看看总结下套路比较好。
设dfs(cur, hasPoint, k, dis)表示,现在处理到cur这个节点,离cur最近的那个仓库节点是hasPoint, 剩下k次设置仓库的机会,还有就是cur的爸爸距离hasPoint的距离。
dfs的时候,对于当前的这个cur点,要么设置为仓库,要么不设。
那么,对于这个cur节点的子树,分配多少次设置工厂的机会给它,也要暴力枚举。
Lchild[cur] cur这个节点的儿子
Rchild[cur] cur这个节点的兄弟
然后dfs下去,我也不知道具体怎么说了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> #include <bitset> const int maxn = 1e2 + 20; int Lchild[maxn], Rchild[maxn], dp[maxn][maxn][maxn]; int a[maxn], fa[maxn], len[maxn]; int dfs(int cur, int hasPoint, int k, int dis) { if (cur == -1 || hasPoint == -1) return 0; if (dp[cur][hasPoint][k] != inf) return dp[cur][hasPoint][k]; int &now = dp[cur][hasPoint][k]; //引用改值 for (int i = 0; i <= k; ++i) { //这个cur节点不做中转站。 now = min(now, dfs(Lchild[cur], hasPoint, i, dis + len[cur]) + dfs(Rchild[cur], hasPoint, k - i, dis) + a[cur] * (dis + len[cur])); } for (int i = 0; i < k; ++i) { // 这个点用来中转 now = min(now, dfs(Lchild[cur], cur, i, 0) + dfs(Rchild[cur], hasPoint, k - i - 1, dis)); } return dp[cur][hasPoint][k]; } void work() { int n, k; cin >> n >> k; memset(dp, 0x3f, sizeof dp); memset(Lchild, -1, sizeof Lchild); memset(Rchild, -1, sizeof Rchild); for (int i = 1; i <= n; ++i) { cin >> a[i] >> fa[i] >> len[i]; Rchild[i] = Lchild[fa[i]]; Lchild[fa[i]] = i; } cout << dfs(0, 0, k, 0) << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif work(); return 0; }
Vijos p1518河流 树形DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。