poj3342Party at Hali-Bula(树形dp)
2024-08-24 09:37:12
/*
树形dp!
判重思路:
当dp[v][0]==dp[v][1]时,很自然,flag[u][0]必然是有两种方案的。flag[u][1]则不然,
因为它只和dp[v][0]有关系。而若flag[v][0]不唯一时,则必然flag[u][1]也不唯一
也就是u的子节点有dp[v][1]==dp[v][0](选与不选都一样),那么父节点u不选的时候一定会有
多种方案!也就是flag[u][0]=false; 否则如果flag[v][0]==flase(子节点不选的时候有多种方案),
那么父节点u选择的时候一定有多种方案,则flag[u][1]=false;
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
#include<algorithm>
#define N 205
using namespace std; map<string, int>mp;
int n;
int cnt;
int g[N][N];
int dp[N][];
bool flag[N][];
map<string, int>::iterator it; void dfs(int u){
for(int v=; v<=n; ++v)
if(g[u][v]){
dfs(v);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][], dp[v][]);
if(dp[v][]==dp[v][]) flag[u][]=false;
if(flag[v][]==false) flag[u][]=false;
}
} int main(){
string na1, na2;
while(scanf("%d", &n) && n){
mp.clear();
memset(g, , sizeof(g));
cnt=;
cin>>na1;
mp[na1]=++cnt;
for(int i=; i<n; ++i){
dp[i][]=;
dp[i][]=;
flag[i][]=flag[i][]=true;
cin>>na1>>na2;
it=mp.find(na1);
if(it==mp.end())
mp[na1]=++cnt;
it=mp.find(na2);
if(it==mp.end())
mp[na2]=++cnt;
g[mp[na2]][mp[na1]]=;
}
dp[n][]=;
dp[n][]=;
flag[n][]=flag[n][]=true;
dfs();
if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else if(dp[][]>dp[][] && flag[][]) printf("%d %s\n", dp[][], "Yes");
else printf("%d %s\n", max(dp[][], dp[][]), "No");
}
return ;
}
最新文章
- Swift来的正是时候
- scala多个构造函数的定义方法
- Python3基础 assert关键字 成功啥事没有,失败了就报错
- 【web】web欢迎页面执行servlet
- FKCL-OS&mdash;&mdash;自主的操作系统
- web安全之SQL注入
- 微信小程序 Request faild 请求后台失败
- DWR第二篇之逆向Ajax
- weblogic/tomcat Get乱码【转】
- 各种梯度下降 bgd sgd mbgd adam
- Jmeter分离登录事务的另一种方式
- Android软件开发之盘点全部Dialog对话框大合集(一)
- (object) array
- Android APP 分享图片文字到微信刚開始正常,后面就不弹出分享框了
- Beta阶段第三次网络会议
- Android系统移植与调试之------->如何修改Android手机NFC模块,使黑屏时候能够使用NFC
- 字符编码:WideCharToMultiByte
- C#.net制作验证码(英文与数字组成的4位随机数),以及MD5值的使用
- iOS 总结网页常用的东西
- 百亿级企业级 RPC 框架开源了!
热门文章
- spring AOP应用
- link2001错误无法解析外部符号metaObject
- PHP, LDAPS and Apache
- php CLI 模式下的传参方法
- (转)将win7电脑无线网变身WiFi热点,让手机、笔记本共享上网
- samba server install
- Tableau:数据可视化之急速BI
- Java多线程20:多线程下的其他组件之CountDownLatch、Semaphore、Exchanger
- WPF,Silverlight与XAML读书笔记第四十八 - Silverlight网络与通讯
- TDD(测试驱动开发)培训录