F. Economic Difficulties

题目链接:

https://codeforces.com/contest/1263/problem/F

题目大意:

两棵树,都有n个叶子节点,一棵树正着放,一棵树倒着放,叶子节点从左到右对应装置1,2,3,4...n,问最多能删掉多少条边,使得装置能与两棵树任意一个根节点1相连。

解题思路:

mp[ i ][ j ]是装置 i 到 j 这段区间删除这段连续区间所能删除的最大边数,两个图分开看,算出每一个图中如果不连通这段区间对应的叶子节点所能删除的最大边数,取这两个图的最大值就是mp[ i ][ j ]。dp[ i ]代表前 i 个装置中的最大删除数,因此可以推出递推式dp[ i ]=max(dp[ i ],dp[j] + mp[ j ][ i ] ) 其中j是从0 - i。

代码:

 #include <bits/stdc++.h>
using namespace std;
const int N=3e3;
const int maxn=1e9+;
const int minn=;
vector<int>arr[N];//存图
int sz[N];//记录当删除这个点后最多能删除多少条边
int L[N],R[N];//记录第i个节点包含的设备区间中的最左端与最右端
int mp[N][N];//记录选取任意连续区间的设备并删除,可以删除最多几条边(连续是指删除的边在同一个图中)
int dp[N]; int dfs(int a,int pre){
if(a!=){//每个点都代表他上方的那条边,1的上方没有边
sz[a]=;
}
for(int i=;i<arr[a].size();i++){
if(arr[a][i]!=pre){
dfs(arr[a][i],a);
sz[a]+=sz[arr[a][i]];//记录删除这个点会删除多少条边
L[a]=min(L[a],L[arr[a][i]]);//这个点代表区间的左端点
R[a]=max(R[a],R[arr[a][i]]);//右端点
}
}
mp[L[a]][R[a]]=max(mp[L[a]][R[a]],sz[a]);//记录这个区间的最大删除边数
} int main(){
int n,a,b,v;
cin>>n;
for(int i=;i<;i++){
scanf("%d",&a);
for(int i=;i<=N;i++){
arr[i].clear();
L[i]=maxn;//初始化无穷大
R[i]=minn;//0
}
for(int i=;i<a;i++){//存图
scanf("%d",&v);
arr[v].push_back(i+);
arr[i+].push_back(v);
}
for(int i=;i<=n;i++){
scanf("%d",&v);//这个点代表的装置区间为i
R[v]=L[v]=i;
}
sz[]=;
dfs(,);
}
dp[]=;
dp[]=mp[][];
for(int i=;i<=n;i++){
for(int j=;j<=i;j++){
dp[i]=max(dp[i],dp[j]+mp[j+][i]);
}
}
cout<<dp[n]<<endl;
return ;
}

最新文章

  1. jquery mobile
  2. webDriver 执行杀死浏览器进程方法
  3. sql server 2014预览版发布
  4. Android 用代码设置Shape,corners,Gradient
  5. HTML学习之Web存储(五)
  6. 基于bootstrap面板的类别多选栏
  7. Windows下面对环境变量的操作
  8. 02.[WPF]如何固定窗口的大小
  9. 《University Calculus》-chaper13-多重积分-三重积分的引入
  10. qt实现-给SQLITE添加自定义函数
  11. 七、vue中v-for有时候对页面不会重新渲染,数组变化后如何到渲染页面
  12. Mysql数据的增删改查
  13. (87)Wangdao.com第二十天_JavaScript document 节点对象
  14. css实现横向带箭头步骤流程效果
  15. HBase架构设计
  16. HTTP Health Checks
  17. JarvisOJ BASIC -.-字符串
  18. ruia笔记
  19. LeetCode: Binary Search Tree Iterator 解题报告
  20. 【剑指offer】矩形覆盖

热门文章

  1. Java基础/时间日期格式
  2. python面试题--初级(二)
  3. 牛客练习赛46 E 华华和奕奕学物理 (树状数组)
  4. ESP32 Ethernet to wifi
  5. MySQL-快速入门(9)视图
  6. java 数组详细介绍
  7. MATLAB图像的代数运算
  8. LVS集群的ipvsadm命令用法
  9. 分页控件SSTab
  10. hdu 4638 Group(离线+树状数组)