test20180922 扭动的树

题意

分析

二叉查找树按照键值排序的本质是中序遍历，每次我们可以在当前区间中提取出一个根，然后划分为两个子区间做区间DP。记\(f(i,j,k)\)表示区间[i, j]建子树，子树根节点的父亲是第k个数的最大sum值之和。由于k只能为i-1或j+1，故状态数只有\(O(n^2)\)，总复杂度\(O(n^3)\)。

在代码实现中，为了减小空间，f的k那一维可以用0/1表示。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const int MAXN=307;

int n;

ll k[MAXN],v[MAXN],sum[MAXN];

bool e[MAXN][MAXN];

bool vis[MAXN][MAXN][2];

ll f[MAXN][MAXN][2];

ll dp(int l,int r,int fa)

{

	if(l>r)

		return 0;

	if(vis[l][r][fa])

		return f[l][r][fa];

	vis[l][r][fa]=1;

	ll&res=f[l][r][fa]=-1;

	int rt=fa==0?l-1:r+1;

	for(int mid=l;mid<=r;++mid)

		if(e[mid][rt])

		{

			if(dp(l,mid-1,1)==-1||dp(mid+1,r,0)==-1)

				continue;

			res=max(res,f[l][mid-1][1]+f[mid+1][r][0]+sum[r]-sum[l-1]);

		}

	return res;

}

typedef pair<ll,ll> pii;

int main()

{

  freopen("tree.in","r",stdin);

  freopen("tree.out","w",stdout);

	vector<pii>sorted;

	read(n);

	for(int i=1;i<=n;++i)

	{

		static ll x,y;

		read(x);read(y);

		sorted.emplace_back(x,y);

		if(x==1)

		{

			puts("-1");

			return 0;

		}

	}

	sort(sorted.begin(),sorted.end());

	for(int i=1;i<=n;++i)

	{

		tie(k[i],v[i])=sorted[i-1];

		sum[i]=sum[i-1]+v[i];

	}

	for(int i=1;i<n;++i)

		for(int j=i+1;j<=n;++j)

			if(__gcd(k[i],k[j])>1)

				e[i][j]=e[j][i]=1;

	ll ans=-1;

	for(int i=1;i<=n;++i)

	{

		if(dp(1,i-1,1)==-1||dp(i+1,n,0)==-1)

			continue;

		ans=max(ans,f[1][i-1][1]+f[i+1][n][0]+sum[n]);

	}

	printf("%lld\n",ans);

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}