程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> BZOJ 2500 幸福的道路 樹形DP+單調隊列

BZOJ 2500 幸福的道路 樹形DP+單調隊列

編輯:關於C++

題目大意:給定一棵樹,令a[i]為從第i個節點出發的最長鏈,求a[i]中最長的區間,滿足區間內最大值與最小值之差不超過m

讀錯題害死人,腦殘害死人

求a[i]顯然是樹形DP

考慮從一個點出發的鏈可以從子節點走,也可以從父節點走

因此我們DP兩次,第一次求出從子節點走的最長鏈,第二次求出從父節點走的最長鏈,兩次取max就是答案

但是直接DP會有問題,因為從父節點走的最長鏈可能是從自己的子樹出發的,這樣就會走重

因此除記錄從子節點出發的最長鏈外還要記錄一個從另一個子節點出發的次長鏈,如果最長鏈長度相同就從次長鏈走即可

第二問用單調隊列隨便搞搞就好了

時間復雜度O(n)

#include 
#include 
#include 
#include 
#define M 1001001
using namespace std;
struct abcd{
	int to,f,next;
}table[M<<1];
int head[M],tot;
int n,m,ans;
long long f[M],g[M],h[M],a[M];
//f表示從子節點過來的最長鏈
//g表示從子節點過來的次長鏈
//h表示從父節點過來的最長鏈
void Add(int x,int y,int z)
{
	table[++tot].to=y;
	table[tot].f=z;
	table[tot].next=head[x];
	head[x]=tot;
}
void Tree_DP1(int x)
{
	int i;
	for(i=head[x];i;i=table[i].next)
	{
		Tree_DP1(table[i].to);
		if(f[table[i].to]+table[i].f>f[x])
			g[x]=f[x],f[x]=f[table[i].to]+table[i].f;
		else if(f[table[i].to]+table[i].f>g[x])
			g[x]=f[table[i].to]+table[i].f;
	}
}
void Tree_DP2(int x)
{
	int i;
	a[x]=max(f[x],h[x]);
	for(i=head[x];i;i=table[i].next)
	{
		long long temp=( f[x]==f[table[i].to]+table[i].f ? g[x] : f[x] );
		temp=max(temp,h[x]);
		h[table[i].to]=temp+table[i].f;
		Tree_DP2(table[i].to);
	}
}
void Monotonous_Queue()
{
	static int q_max[M],r_max,h_max;
	static int q_min[M],r_min,h_min;
	int i,j;
	for(j=0,i=1;i<=n;i++)
	{
		{
			int *q=q_max,&r=r_max,&h=h_max;
			while( r-h>=1 && a[i]>=a[q[r]] )
				q[r--]=0;
			q[++r]=i;
		}

		{
			int *q=q_min,&r=r_min,&h=h_min;
			while( r-h>=1 && a[i]<=a[q[r]] )
				q[r--]=0;
			q[++r]=i;
		}

		while(a[q_max[h_max+1]]-a[q_min[h_min+1]]>m)
		{
			++j;
			if(q_min[h_min+1]==j)
				q_min[++h_min]=0;
			if(q_max[h_max+1]==j)
				q_max[++h_max]=0;
		}

		ans=max(ans,i-j);
	}
}
int main()
{
	int i,x,y;
	cin>>n>>m;
	for(i=2;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,i,y);
	}
	Tree_DP1(1);
	Tree_DP2(1);
	Monotonous_Queue();
	cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved