codeforces div2_603 F. Economic Difficulties(树dfs预处理+dp)

题目连接：http://codeforces.com/contest/1263/problem/F

题意：有n个设备，上和下分别连接着一颗树，上下两棵树每棵树的叶子节点连接一个设备，两棵树的根节点都是1，1是源点可以发电供给叶结点连接的设备，现在问最多删除多少条边可以保证从根结点1发电后仍然可以使得所有设备都有电？

如上图删除红色的边（5条）仍然可以保证所有设备能供电

思路:

因为是有上下两棵树，所以对于一个设备可以供电，那么删除上面的树一部分边，要么删除下面一部分边，根据题意，我们当然要删除最多的那一部分边。对于边，不太容易枚举，但由于树的特殊性，除根结点外，每个结点的入边只能是一条，即入度为1，我们可以考虑删除一个结点和其所连接的入边，然后来判断一下会影响哪些设备。假设这个节点被删除后，所影响的设备是设备 i 到设备 j 的所有设备,致使它们无法被供电，那我们可以用val[i][j]表示设备 i 到设备 j 不能供电时，可以删除的最多的边数量，这个过程可以用dfs预处理去记录（具体看代码）

上下两颗树都dfs预处理完之后，得到了val数字，就可以dp了，设dp[i]表示对于前i个设备，最多可以删除多少条仍然可以供电

转移方程就比较简单了，dp[i] = max (dp[i] , dp[j] + val [ j+1 ] [ i ] )，j从0枚举到 i-1，最终dp[n]就是所求答案.

AC代码:

#include<iostream>

#include<stack>

#include<vector>

#include<algorithm>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

typedef long long ll;

const int maxn = 2e3+5;

struct node{

	vector<int> next;

}g1[maxn],g2[maxn];

int val[maxn][maxn];

int size1[maxn],size2[maxn],l1[maxn],l2[maxn],r1[maxn],r2[maxn];//枚举可以延申的左右端点 和 边数

int dp[maxn];

void dfs_up(int cur){

	if(cur != 1)  size1[cur] = 1;

	for(int i = 0;i<g1[cur].next.size();i++){

		int v = g1[cur].next[i];

		dfs_up(v);

		l1[cur] = min(l1[cur],l1[v]);

		r1[cur] = max(r1[cur],r1[v]);

		size1[cur]+=size1[v];

	}

	val[l1[cur]][r1[cur]] = max(val[l1[cur]][r1[cur]],size1[cur]);

}

void dfs_down(int cur){

	if(cur != 1)  size2[cur] = 1;//如果不是根节点1，先+1条边，因为该节点上面必定连接一条边

	for(int i = 0;i<g2[cur].next.size() ;i++){

		int v = g2[cur].next[i];

		dfs_down(v);

		l2[cur] = min(l2[cur],l2[v]);

		r2[cur] = max(r2[cur],r2[v]);

		size2[cur]+=size2[v];

	}

	val[l2[cur]][r2[cur]] = max(val[l2[cur]][r2[cur]],size2[cur]);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int n;cin>>n;

    int a;cin>>a;

    for(int i = 1;i<a;i++){

    	int pi;cin>>pi;

    	l1[i] = maxn,r1[i] = -1;

    	g1[pi].next.push_back(i+1);

	}

	l1[a] = maxn,r1[a] = -1;

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

		int xi;cin>>xi;

		l1[xi] = i,r1[xi] = i;

	}

	int b;cin>>b;

	for(int i = 1;i<b;i++){

		int qi;cin>>qi;

    	l2[i] = maxn,r2[i] = -1;

		g2[qi].next.push_back(i+1);

	}

	l2[b] = maxn,r2[b] = -1;

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

		int yi;cin>>yi;

		l2[yi] = i,r2[yi] = i;

	}

	dfs_up(1),dfs_down(1);//上下两颗树各跑一遍dfs

	for(int i = 0;i<=n;i++){

		for(int j = 0;j<i;j++){

			dp[i] = max(dp[i],dp[j]+val[j+1][i]);//n^2dp枚举

		}

	}

	cout<<dp[n];

    return 0;

}

巴特西

codeforces div2_603 F. Economic Difficulties(树dfs预处理+dp)

最新文章

热门文章