POJ 3342 树形DP+Hash
2024-10-01 11:08:45
这是很久很久以前做的一道题,可惜当时WA了一页以后放弃了。
今天我又重新捡了起来。(哈哈1A了)
题意:
没有上司的舞会+判重
思路:
hash一下+树形DP
题目中给的人名hash到数字,再进行运算。
树形DP
f[x][0]+=max(f[x.son][0],f[x.son][1]);
f[x][1]+=f[x.son][0];
f[x][0]表示不选这个节点,f[x][1]表示选这个节点。
如果选了这个节点,那么它的儿子必定不选。
如果不选这个节点,它的儿子们可选可不选 取最大的即可。
然后就是坑爹的判重。
怎么判重呢?
如果n为2的话 肯定是No不用解释了吧
然后就从1到n遍历一遍 如果选这个节点和不选这个节点的人数是一样的就遍历它的儿子 如果有任何一个儿子节点选这个儿子节点和不选这个儿子节点的人数是一样的话 那么就是No
否则就是Yes
// by SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot,num,first[205],v[666],next[666],Hash[1000008],jya,jyb,f[666][2];
char a[105],b[105];
void add(int x,int y){v[tot]=y,next[tot]=first[x],first[x]=tot++;}
void dfs(int x){
f[x][1]=1;
for(int i=first[x];~i;i=next[i]){
dfs(v[i]);
f[x][0]+=max(f[v[i]][0],f[v[i]][1]);
f[x][1]+=f[v[i]][0];
}
}
int main(){
st:while(scanf("%d",&n)&&n){
scanf("%s",a);
jya=tot=0;num=1;memset(first,-1,sizeof(first));
memset(f,0,sizeof(f)),memset(Hash,0,sizeof(Hash));
int len=strlen(a);
for(int i=0;i<len;i++)jya=(jya*256+a[i])%1000007;
Hash[jya]=1;
for(int i=1;i<n;i++){
scanf("%s%s",a,b);
int lena=strlen(a),lenb=strlen(b);jya=jyb=0;
for(int i=0;i<lena;i++)jya=(jya*256+a[i])%1000007;
if(!Hash[jya])Hash[jya]=++num;
for(int i=0;i<lenb;i++)jyb=(jyb*256+b[i])%1000007;
if(!Hash[jyb])Hash[jyb]=++num;
add(Hash[jyb],Hash[jya]);
}
if(n==2){puts("1 No");goto st;}
dfs(1);
printf("%d ",max(f[1][0],f[1][1]));
for(int i=1;i<=n;i++)
if(f[i][0]==f[i][1])
for(int j=first[i];~j;j=next[j])
if(f[v[j]][0]==f[v[j]][1]){puts("No");goto st;}
puts("Yes");
}
}
最新文章
- js 数组
- iOS-地图报错超出了经纬度范围Invalid Region
- CSS布局概述
- ezSQL 数据库操作类
- CentOS 7 +Nginx
- 【图像识别】 图像处理和图像分析(leptonica)leptonica-1.68安装配置 (vs2008)
- 第三届蓝桥杯Java高职组决赛第三题
- FTP上传文件时 System.Net.WebException: 基础连接已经关闭: 接收时发生错误。
- 团队作业4——第一次项目冲刺(Alpha版本)4.25
- volatile关键字是如何起作用的?
- vi使用手册
- Python使用Plotly绘图工具,绘制面积图
- 关于 DotNetCore 的自定义权限管理
- 自学Linux Shell9.3-基于Red Hat系统工具包:RPM属性依赖的解决方式-YUM在线升级
- cxgrid多选删除
- MYsql系统函数和联合查询
- spring学习 8-面试(事务,解决线程安全)
- [CodeForces-763C]Timofey and remoduling
- 实际用户ID,有效用户ID,保存的设置用户ID
- 实战maven私有仓库三部曲之三:Docker下搭建maven私有仓库
热门文章
- CXF2.7.7 java.lang.RuntimeException: Cannot create a secure XMLInputFactory
- JavaScript DOM编程艺术(第2版)学习笔记1(1~4章)
- 如何使用pgpool failover_stream.sh自己控制选择指定的master节点
- Apache2.2伪静态配置
- java的-D命令行参数 mvn -D参数
- cache(缓存)的作用
- 【AnjularJS系列6 】 过滤器
- struts2配置 匹配原则 配置各项默认
- PAT 天梯赛练习集 L2-004. 这是二叉搜索树吗?
- jQuery 事件流的概念