HDU 6178 Monkeys

 2023-09-05 阅读 349 评论 0

摘要:题意:给出一棵 N 个节点树,上面有 K 个猴子,然后竟可能删边,但是每一只猴子必须有直接相邻的猴子与之相邻。求最少剩下几条边。 分析:一条边可以用两只猴子站,这样的一条点对,越多越好,如果是ans个,ans*2>

题意:给出一棵 N 个节点树,上面有 K 个猴子,然后竟可能删边,但是每一只猴子必须有直接相邻的猴子与之相邻。求最少剩下几条边。

 

分析:一条边可以用两只猴子站,这样的一条点对,越多越好,如果是ans个,ans*2>=k,那么只需要 (k+1)/2 条边。

否则,需要  ans + (k-ans*2) 条边。

现在问题就转为求这样的点对有多少,哈哈,有漏洞的DP都AC了,哈哈~~~~。

我发现标程思路也是这样,哈哈,都是bug程序!!!

唯一的解释就是 d[u][1] >= d[u][0] 感性认识

#include <bits/stdc++.h>using namespace std;const int maxn = 100005;vector<int> g[maxn];/*------- 开挂 -------*/
namespace fastIO {#define BUF_SIZE 100000// fread -> readbool IOerror = 0;char nc() {static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;if(pl == pr) {pl = buf;pr = buf + fread(buf, 1, BUF_SIZE, stdin);if(pr == pl) {IOerror = 1;return -1;}}return *pl++;}inline bool blank(char ch) {return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';}void read(int &x) {char ch;while(blank(ch = nc()));if(IOerror)return;for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');}#undef BUF_SIZE
};
using namespace fastIO;
/*------- 完结 -------*/int d[maxn][2]; // 0 匹配
bool vis[maxn];void dp(int u,int fa) {if(vis[u]) return;vis[u] = 1;d[u][0] = d[u][1] = 0;int sum = 0;for(int i=0; i < (int)g[u].size(); i++) {int v = g[u][i];if(v==fa) continue;dp(v,u);d[u][1] += max(d[v][0],d[v][1]);sum+=d[v][0];}for(int i=0; i < (int)g[u].size(); i++) {int v = g[u][i];if(v==fa) continue;d[u][0] = max(d[u][0],sum-d[v][0]+d[v][1]+1);}}int T;
int N,K;
int main()
{//freopen("in.txt","r",stdin);
    read(T);while(T--) {read(N);read(K);for(int i=0; i <= N; i++)g[i].clear();memset(vis,0,sizeof(vis));int u;for(int i=1; i < N; i++) {read(u);g[u].push_back(i+1);g[i+1].push_back(u);}dp(1,-1);int ans = max(d[1][1],d[1][0]);if(ans*2>=K)printf("%d\n",(K+1)/2);elseprintf("%d\n",ans+K-(ans*2));}return 0;
}

 

转载于:https://www.cnblogs.com/TreeDream/p/7426998.html

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/481.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息