UPC 圣诞树（DAG模型）

假设圣诞树从1层到n层的排列形式是类似于一张链状的图，那么在其边缘衍生出的若干条指向下层某元素的边与链状图就组成了一张有向无环图（只能指向一个元素且下层元素不可指向上层）。对每个点进行记忆化搜索（状态转移：现在的值加上以下所连接的值），再取最大值即可。

//#include<pch.h> #include <iostream> #include <cstdio> #include <bits/stdc++.h> #include <map> #include <algorithm> #include <stack> #include <iomanip> #include <cstring> #include <cmath> #define DETERMINATION main #define lldin(a) scanf_s("%lld", &a) #define println(a) printf("%lld\n", a) #define reset(a, b) memset(a, b, sizeof(a)) const int INF = 0x3f3f3f3f; using namespace std; const double PI = acos(-1); typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int mod = 1000000007; const int tool_const = 19991126; const int tool_const2 = 2000; inline ll lldcin() { ll tmp = 0, si = 1; char c; c = getchar(); while (c > '9' || c < '0') { if (c == '-') si = -1; c = getchar(); } while (c >= '0' && c <= '9') { tmp = tmp * 10 + c - '0'; c = getchar(); } return si * tmp; } ///Untersee Boot IXD2(1942) /**Although there will be many obstructs ahead, the desire for victory still fills you with determination..**/ /**Last Remote**/ ll rel[200][200],gifts[200],dp[200]; bool vis[2000]; string tmp; void deal(ll index)//处理读入的数据 { ll cnt = 0,tmp2=0; tmp += " "; for (int i = 0; tmp[i]; i++) { if (tmp[i] == ' ') { if (cnt == 0) gifts[index] = tmp2; else rel[index][tmp2] = 1; tmp2 = 0; cnt++; } else tmp2 = tmp2 * 10 + (tmp[i] - '0'); } } ll dfs(ll current,ll lim)//记忆化搜索 { ll &tmp5 = dp[current]; if (vis[current]) return tmp5; else { vis[current] = 1; for (int i = 1; i <= lim; i++) { if (rel[current][i]) { tmp5 = max(tmp5, dfs(i, lim)+gifts[current]);//状态转移方程 //cout << tmp5 << endl; } } return tmp5; } } int DETERMINATION() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); ll n; cin >> n; cin.get(); for (int i = 1; i <= n; i++) { getline(cin, tmp); deal(i); tmp = ""; } /*for (int i = 1; i <= n; i++) cout << gifts[i] << " "; cout << endl; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << rel[i][j] << " "; } cout << endl; }*/ for (int i = 1; i <= n; i++) dp[i] = gifts[i]; ll ans = -1; for (int i = 1; i <= n; i++) ans = max(ans, dfs(i, n)); cout << ans << endl; return 0; }

网址：UPC 圣诞树（DAG模型） http://c.mxgxt.com/news/view/832427

相关内容

刺激战场网红小圣诞树是什么
圣诞夜惊魂
京圈大小姐周扬青的圣诞树竟然引爆了全网，太惊人了！
尹浩宇 世界上最滑稽的圣诞树
毕雯珺李一桐同款圣诞树、窗帘及地板：疑似恋情曝光！
刘嘉玲晒抱俩新家庭成员合照！豪宅摆2米高圣诞树，被亲满脸慈爱
圣诞歌曲
因果图模型：理解因果关系的强大工具
贝克汉姆长子在岳父家欢度圣诞，并与妻子圣诞树前秀恩爱
圣诞节穿什么？来看女明星的示范，新垣结衣太朴素，IU才值得学

随便看看