FZOJ 2274 二分+有源汇上下界最小流
HDU 5957 环套树+线段树维护bfs序

HDU5956 The Elder 下凸壳的维护

zjhl2 posted @ 2017年9月20日 15:45 in with tags 动态规划 凸包 DFS 树形DP 二分 , 1253 阅读

题意:

一棵树,1为根。每个点只能走向祖先,时间为距离的平方,另外走到祖先后会停留P单位时间。求每个点到达根的最小时间的最大值。

 

思路:

显然dp方程为:f[i]=(d[i]-d[j])^2+P+f[j]  ( j 是 i 的祖先)

转化成向量点积形式:f[i]=d[i]^2+P+(1 , 2*d[i] ) * ( f[j]+d[j]^2 , -d[j] )

注意到深度越大,向量(1 , 2*d[i] )会逆时针旋转

于是维护点集i的所有祖先的  ( f[j]+d[j]^2 , -d[j] ) 的下凸壳,就能求出f[i]的最小值

注意到向量( f[j]+d[j]^2 , -d[j] )只会添加在下凸壳右边,于是只要用个队列来保存就可以了

查询的时候只要一直扔掉左边的点,找到最大值为止,然后退出当前dfs的时候加回来就可以了

如果一个个保存删掉的点,再一个个加回来的话,在菊花图的情况下复杂度就会变成O(n^2),事实上目前网上的题解都是这么做的,估计出题人也没意识到复杂度的问题,因为这看起来很像O(n)。

我的做法是每次dfs记录当前队列的左端点,和右端点,操作完后,事实上只是替换了数组里的tail位置的元素,把head和tail还有这个元素事先保存下来,最后恢复head,tail和这个元素就可以了,这样复杂度就是完美的O(n)了。

也不知道这种做法叫什么,毕竟自己乱想出来的,就叫回溯队列好了233

后来一想这个做法还是n方。。。因为每次head和tail的删除操作都可能是O(n)的,所以要二分查找head和tail分别应该删到哪,这样算法复杂度就是O(nlogn)了

这里如果不用斜率,而把两边的dx都乘到对面去的话是有问题的,因为f[j]+d[j]^2的规模是1e14,2*d[i]的规模是1e7,乘起来理论上会爆,然而数据好像还是没卡掉这种做法

 

代码1:O(n^2)做法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
	ll x,y;
	ll operator*(const P &b)const
	{
		return x*b.x+y*b.y;
	}
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
	long double tmp=1.0;
	return tmp*(b.y-a.y)/(b.x-a.x);
}
void dfs(int u,int fa,int deep)
{
	int phead=head,ptail=tail;
	d[u]=deep;
	if (u==1) f[u]=-p;
	else
	{
		P tmp={1,2*d[u]};
		while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
		f[u]=d[u]*d[u]+p+stk[head]*tmp;
	}
	P tmp={f[u]+d[u]*d[u],-d[u]};
	while(tail-head+1>=2&&
		slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
	P mem=stk[tail+1];
	stk[++tail]=tmp;

	for (int i=0;i<link[u].size();i++)
	{
		int v=link[u][i].x;
		if (v==fa) continue;
		dfs(v,u,deep+link[u][i].y);
	}
	tail--;
	stk[tail+1]=mem;
	head=phead; tail=ptail;
}
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&p);
		for (int i=1;i<n;i++)
		{
			ll x,y,z;
			scanf("%d%d%lld",&x,&y,&z);
			if (z<0) n/=0;
			link[x].push_back({y,z});
		}
		head=1; tail=0;
		dfs(1,1,0);
		ll ans=0;
		for (int i=1;i<=n;i++) ans=max(ans,f[i]);
		printf("%lld\n",ans);

		for (int i=1;i<=n;i++) link[i].clear();
	}
}

 

代码2:O(nlogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100005;
struct P
{
    ll x,y;
    ll operator*(const P &b)const
    {
        return x*b.x+y*b.y;
    }
}stk[N];
int n,p;
int head,tail;
vector<P>link[N];
ll f[N],d[N];
long double slope(P a,P b)
{
    long double tmp=1.0;
    return tmp*(b.y-a.y)/(b.x-a.x);
}
int gethead(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (stk[mid]*v>=stk[mid+1]*v) l=mid+1;
		else r=mid;
	}
	return l;
}
int gettail(P v)
{
	int l=head,r=tail;
	while(l<r)
	{
		int mid=(l+r)/2;
		if (slope(stk[mid],stk[mid+1])<slope(stk[mid+1],v)) l=mid+1;
		else r=mid;
	}
	return l;
}
void dfs(int u,int fa,int deep)
{
    int phead=head,ptail=tail;
    d[u]=deep;
    if (u==1) f[u]=-p;
    else
    {
        P tmp={1,2*d[u]};
        head=gethead(tmp);

        //while(tail-head+1>=2&&stk[head]*tmp>=stk[head+1]*tmp) head++;
        f[u]=d[u]*d[u]+p+stk[head]*tmp;
    }
    P tmp={f[u]+d[u]*d[u],-d[u]};
    tail=gettail(tmp);
//    while(tail-head+1>=2&&
//        slope(stk[tail-1],stk[tail])>=slope(stk[tail],tmp)) tail--;
    P mem=stk[tail+1];
    stk[++tail]=tmp;

    for (int i=0;i<link[u].size();i++)
    {
        int v=link[u][i].x;
        if (v==fa) continue;
        dfs(v,u,deep+link[u][i].y);
    }
    tail--;
    stk[tail+1]=mem;
    head=phead; tail=ptail;
}
int main()
{
    int t; scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&p);
        for (int i=1;i<n;i++)
        {
            ll x,y,z;
            scanf("%d%d%lld",&x,&y,&z);
            link[x].push_back({y,z});
        }
        head=1; tail=0;
        dfs(1,1,0);
        ll ans=0;
        for (int i=1;i<=n;i++) ans=max(ans,f[i]);
        printf("%lld\n",ans);

        for (int i=1;i<=n;i++) link[i].clear();
    }
}
Avatar_small
SBI savings account 说:
2022年8月03日 17:54

Bank savings interest rate is valid, if the customer maintained the minimum amount in their savings accounts, and the Interest Rate of State Bank of India varies every year based on budget session and thus by having your savings account will also earn you extra money. SBI savings account interest rate This rate is paid by financial institutions based on the deposit done in a once saving account and thus the amount gets added in the current principal savings balance. Choose better savings accounts in State Bank of India to drive an extra source of income without any risky investments, and the Interest Rate of SBI accounts and Deposits is far different from the SBI Fixed deposits.

Avatar_small
www.thezeusnetwork.c 说:
2023年7月11日 05:24

Zeus Network provides a dedicated Zeus free trial. Sadly, Zeus does not provide a Zeus free trial period before the membership. The Zeus Network, including documentaries, drama series and reality shows. www.thezeusnetwork.com/activate code firestick Once after downloading, open the application, and “activate Zeus Network” at “thezeusnetwork.com/activate” in search of the available content. Zeus Network without a connecting TV broadcasting service provider the Zeus Network app is available on popular streaming devices.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter