思路

这道题是一道十分巧妙的树形DP。

其中

dpl_{x,i}

表示以结点

x

为根的子树当中，等差数列的首项为

i

是否可行。

dpr_{x,i}

表示已结点

x

为根的子树中等差数列末项为

x

为根是否可行。其中

dpl_{x,i}

中的

i

要满足

i \le v_u

，

dpr_{x,i}

中的

i

要满足

i \ge v_u

（题目要求当选了一个结点后必须选它的上司，与就是父亲结点）。

那对于

dpl_{x,i}=1

需要

x

的一个子节点

y

中

dpl_{y,i}=1

。然后发现，如果想要让

dpl_{x,i}=1

，还需要让

y

的整颗子树能与

x

组成等差数列，并且必须是与笑话编号比

x

小的组成，不然它就无法成为等差数列的首项。既然必须是

x

的首项，那

y

中就必须是末项。

对于

dpr_{x,i}

是一样的，只需把上面全都反过来。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int n,v[20000],h[20000],ne[20000],e[20000],idx,l[20000][200],r[20000][200];
void add(int u,int v){
	e[idx]=v,ne[idx]=h[u],h[u]=idx++;
} 
void dfs(int x){
	vector<int> tl,tr;
	for(int i=h[x];~i;i=ne[i]){
		int j=e[i];
		dfs(j);
		if(v[j]<v[x]) tl.push_back(j);
		if(v[j]>v[x]) tr.push_back(j);
	}
	l[x][v[x]]=1,r[x][v[x]]=1;
	for(int i=v[x]-1;i>=1;i--){
		for(auto p:tl){
			if(l[p][i]){
				for(int j=i;j<v[x];j++){
					if(r[p][j]&&l[x][j+1]){
						l[x][i]=1;
						break;
					}
				}
			}
		} 
	}
	for(int i=v[x]+1;i<=100;i++){
		for(auto p:tr){
			if(r[p][i]){
				for(int j=v[x]+1;j<=i;j++){
					if(l[p][j]&&r[x][j-1]){
						r[x][i]=1;
						break;
					}
				}
			}
		} 
	}
}
int main(){
	memset(h,-1,sizeof(h));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	dfs(1);
	int lans=0,rans=0;
	for(int i=1;i<=100;i++){
		lans+=l[1][i];
		rans+=r[1][i]; 
	}
	cout<<lans*rans;
	return 0;
}

题解：P6534 [COCI 2015/2016 #1] UZASTOPNI

文章操作

思路

Code

相关推荐

评论

题解：P6534 [COCI 2015/2016 #1] UZASTOPNI