NOIP模拟（10.23）T3 拆网线

本文主要是介绍NOIP模拟（10.23）T3 拆网线，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目背景：

10.23 NOIP模拟T3

分析：DP + 贪心

 

显然最好的连接方式就是，k / 2对企鹅，每队一条边，肯定是最优的，如果不能满足当然是先选尽量多对，然后其他的每一只连一条边连到某一个集合中去，（对于一个没有组成对的点，周围一定都是组好队的点，否则就可以新加入一对了），那么我们只需要找最大能组成多少对就好了，这个小小的DP一下就可以了。

定义dp[i][0/1]表示，0：以i为根的子树，i（0：没有选择， 1：被选择了）了，的最大对数为dp[i][0/1]状态,转移很简洁。

最后输出时判断一下，num = max(dp[root][0],dp[root][1])

若num * 2 >= k, ans = k / 2 + (k & 1)

若num * 2 < k, ans = k - num;

 

Source：

/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>const int MAXN = 100000 + 1000;int n, k, x, t, num;
std::vector<int> edge[MAXN];
int dp[MAXN][2];inline void add_edge(int x, int y) {edge[x].push_back(y), edge[y].push_back(x);
}inline void read_in() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; ++i) edge[i].clear();for (int i = 1; i < n; ++i) scanf("%d", &x), add_edge(x, i + 1);
}inline void dfs(int cur, int fa) {int sum = 0;dp[cur][0] = dp[cur][1] = 0;for (int p = 0; p < edge[cur].size(); ++p) {int v = edge[cur][p];if (v != fa) dfs(v, cur), sum += std::max(dp[v][0], dp[v][1]);}dp[cur][0] = sum;for (int p = 0; p < edge[cur].size(); ++p) {int v = edge[cur][p];if (v != fa) dp[cur][1] = std::max(dp[cur][1], sum - std::max(dp[v][0], dp[v][1]) + dp[v][0] + 1);}
}inline void solve() {dfs(1, 0), num = std::max(dp[1][0], dp[1][1]);if (num * 2 >= k) std::cout << (k / 2 + (k & 1)) << '\n';else std::cout << k - num << '\n';
}int main() {
//	freopen("tree.in", "r", stdin);
//	freopen("tree.out", "w", stdout);scanf("%d", &t);while (t--) read_in(), solve();return 0;
}

这篇关于NOIP模拟（10.23）T3 拆网线的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---