Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课《ACM/ICPC竞赛训练》面向全球招生!

解题报告

Posted by hzoi2017_zyc at 2018-05-15 12:36:40 on Problem 3345
树形DP
	看起来是一道树形DP
	其实这就是一道树形DP
	但是......
	根本没考DP,纯粹是个板子
	精粹全在读入~
读入手法:
	首先要明确,'#'只出现在最后
	对于'#'的处理,其实只要用scanf就可以
	scanf输入时的返回值有如下几类
		1.当输入与格式符("%d")统一时,读入几个变量
		  返回值就是几
		2.当输入与格式符不统一时,如用("%d"读入'#')
		  返回值是0
		3.当读入EOF是返回值是-1
	因此,对于'#',可以直接如下处理
		while(scanf("%d%d",&n,&m)!=0){
		}
	即可 
	
	其次对于村庄名,最好用scanf("%s")去读
	不会吃掉空格和回车,不建议用cin>>处理
	中间用getchar()去判断空格和回车
	
	建树的时候自然是用STL的map去建立
	string(可以直接用char[]转化)和int
	之间的映射(记得清空)
	
	代码实现:
		map<string,int>cz;
		char r[205]; 
		int l;//记录映射值 
		for(i=1;i<=n;i++){
			scanf("%s",r);
			if(!cz.count(r))//首参量存在返回1,不存在返回0
				cz[r]=++l;//次参量未知,find难以使用 
			j=cz[r];
			scanf("%d",&hf[j]);
			while(getchar()!='\n'){
				scanf("%s",r);
				if(!cz.count(r))
					cz[r]=++l;
				a++;
				dl[a].zd=cz[r];
				dl[a].lj=qd[j];
				qd[j]=a;
				fw[cz[r]]=true;//记录是否为叶节点 
			}
		}
DP部分:
	实话说,除了读入,这就是道水题
	倒序循环j,正序循环k,正常DP就可以啦

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator