Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 2431 | Accepted: 1294 |
5 0 0 -2 0 1 1 1 0 1 0 -1 1 -1 0 1
2 题目意思真绕,大致上是在给的点里选择若干个点使权值和最大,并且原给出的点构成一棵无根树。一开始没理解样例,后来发现就是把所有的点都选上。 建树: 题目意思已经说了已经是构成树了,所以只要把相邻的节点连接起来就好。 转移:dp[t][0(/1)] 表示以t为根节点的子树在不选择(/选择)t节点的情况下的最大权和。 dp[t][0] = max(max(dp[ti][0], dp[ti][1])); // 子树状态随意,但只能选一个,因为根节点没有选择无法连接多棵子树。 dp[t][1] = sum(dp[ti][0]>0); // 所有权和大于0的子树均可以选入,也可能没有选入一棵子树。
#include <cmath> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int INF = 999999999; std::vector<int > v[1010]; struct Node { int x; int y; int c; }a[1010]; int dp[1010][2]; void link (int _a, int _b) { if (abs(a[_a].x - a[_b].x) + abs(a[_a].y - a[_b].y) == 1) { v[_a].push_back(_b); v[_b].push_back(_a); } } void Tdp(int t, int fa) { dp[t][0] = 0; dp[t][1] = a[t].c; int flag = -INF; for (int i=0; i<v[t].size(); i++) { if (v[t][i] == fa) continue; int _t = v[t][i]; Tdp(_t, t); dp[t][0] = max(dp[t][0], max(dp[_t][0], dp[_t][1])); if (dp[_t][1] > 0) { dp[t][1] += dp[_t][1]; } } } int main () { int n; cin >> n; for (int i=0; i<n; i++) { cin >> a[i].x >> a[i].y >> a[i].c; } for (int i=0; i<n; i++) { for (int j=i+1; j<n; j++) { link(i, j); } } Tdp(0, -1); cout << max(dp[0][0], dp[0][1]) <<endl; return 0; }
原文:http://blog.csdn.net/xuelanghu407/article/details/44604717