首页 > ACM题库 > HDU-杭电 > HDU 4274-Spy’s Work-动态规划-[解题报告]HOJ
2015
05-23

HDU 4274-Spy’s Work-动态规划-[解题报告]HOJ

Spy’s Work

问题描述 :

I’m a manager of a large trading company, called ACM, and responsible for the market research. Recently, another trading company, called ICPC, is set up suddenly. It’s obvious that we are the competitor to each other now!
To get some information about ICPC, I have learned a lot about it. ICPC has N staffs now (numbered from 1 to N, and boss is 1), and anybody has at most one superior. To increase the efficiency of the whole company, the company contains N departments and the ith department is led by the ith staff. All subordinates of the ith staff are also belong to the ith department.
Last week, we hire a spy stealing into ICPC to get some information about salaries of staffs. Not getting the detail about each one, the spy only gets some information about some departments: the sum of the salaries of staff s working for the ith department is less than (more than or equal to) w. Although the some inaccurate information, we can also get some important intelligence from it.
Now I only concerned about whether the spy is telling a lie to us, that is to say, there will be some conflicts in the information. So I invite you, the talented programmer, to help me check the correction of the information. Pay attention, my dear friend, each staff of ICPC will always get a salary even if it just 1 dollar!

输入:

There are multiple test cases.
The first line is an integer N. (1 <= N <= 10,000)
Each line i from 2 to N lines contains an integer x indicating the xth staff is the ith staff’s superior(x<i).
The next line contains an integer M indicating the number of information from spy. (1 <= M <= 10,000)
The next M lines have the form like (x < (> or =) w), indicating the sum of the xth department is less than(more than or equal to) w (1 <= w <=100,000,000)

输出:

There are multiple test cases.
The first line is an integer N. (1 <= N <= 10,000)
Each line i from 2 to N lines contains an integer x indicating the xth staff is the ith staff’s superior(x<i).
The next line contains an integer M indicating the number of information from spy. (1 <= M <= 10,000)
The next M lines have the form like (x < (> or =) w), indicating the sum of the xth department is less than(more than or equal to) w (1 <= w <=100,000,000)

样例输入:

5
1
1
3
3
3
1 < 6
3 = 4
2 = 2

5
1
1
3
3
3
1 > 5
3 = 4
2 = 2

样例输出:

Lie
True

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by—cxlove 

题目:给出一棵树,给出一些子树的权值关系,问是否矛盾

http://acm.hdu.edu.cn/showproblem.php?pid=4274 

初始对于所有结点以及子树的下限为1,上限可能不确定

然后通过给出的不等式去更新上下界,之后进行树形DP,通过孩子的下界更新父节点的下界

再判断是否矛盾

注意当前节点当个的权值下限为1,该节点的下限为孩子下界的和+1

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#define inf 110000000
#define M 10005
#define N 10005
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000007
using namespace std;
struct Node{
	int v,next;
}edge[N*2];
int n,start[N],tot;
int up[N],low[N];
void addedge(int u,int v){
	edge[tot].v=v;
	edge[tot].next=start[u];
	start[u]=tot++;
}
void _addedge(int u,int v){
	addedge(u,v);
	addedge(v,u);
}
bool ans;
void dfs(int u,int pre){
	if(ans) return;
	if(up[u]!=-1&&low[u]>up[u]){ans=true;return;}
	int tmp=0;
	int leaf=1;
	for(int i=start[u];i!=-1;i=edge[i].next){
		int v=edge[i].v;
		if(v==pre) continue;
		dfs(v,u);
		leaf=0;
		tmp+=low[v];
	}
	if(leaf) return;
	low[u]=max(tmp+1,low[u]);
	if(up[u]!=-1&&low[u]>up[u]) ans=true;
}
int main(){
	while(scanf("%d",&n)!=EOF){
		tot=0;mem(start,-1);
		for(int i=2;i<=n;i++){
			int u;
			scanf("%d",&u);
			_addedge(u,i);
		}
		int m;
		for(int i=1;i<=n;i++){low[i]=1;up[i]=-1;}
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			int u,w;
			char str[5];
			scanf("%d%s%d",&u,str,&w);
			if(str[0]=='<') up[u]=w-1;
			else if(str[0]=='>') low[u]=w+1;
			else low[u]=up[u]=w;
		}
		ans=false;
		dfs(1,0);
		puts(ans?"Lie":"True");
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/acm_cxlove/article/details/7967135