专栏首页wym种树 差分约束|贪心

种树 差分约束|贪心

 先看贪心版本。

每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。

然后遍历每个区间统计第i个区间种了k个树,若k大于 t ,则continue, 否则从区间末尾往前种树。 

//贪心种树 
#include <bits/stdc++.h>
using namespace std;
struct N{
	int s,t,e;
	bool operator < (const N b)const {
		return e<b.e;
	}
};
N node[30005];
int book[30005];
int n,m;
int main()
{
	scanf("%d",&n);
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&node[i].s,&node[i].e,&node[i].t);
	}
	sort(node,node+m);
	int ans=0;
	for(int i =0;i<m;i++){
		int k = 0;
		for(int j = node[i].s;j<=node[i].e;j++)if(book[j])k++;
		if(k>=node[i].t)continue;
		for(int j=node[i].e;j>=node[i].s;j--){
			if(!book[j]){
				book[j]=1;
				k++; ans++;
				if(k>=node[i].t)break;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
 } 

差分约束

题目中有这么几个约束条件

sum[i]是 i 的前缀和。

从u到v: sum[u-1] - sum[v] <= - t

从i-1到i:   sum[i] - sum[i-1] <=1  

从i到i-1:   sum[i-1] - sum[ i ]<=0

最后找一个源点也即N+1,N+1到每个点距离为0   sum[i] - sum[N+1]=0

//差分种树 
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
#define R register
struct N{
	int v,nxt,w;
};
int cnt,n,m;
int S;
N edge[100005];
int head[100005],dis[30005],book[30005];
int read(){
	int x=0,dign=1;
	char c = getchar();
	while(c<'0'||c>'9'){
		if(c=='-')dign=-1;
		c = getchar();
	}
	while(c>='0'&&c<='9'){
		x = x*10 + c - '0';
		c = getchar();
	}
	return x*dign;
}
void add(int u,int v,int w){
	cnt++;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].nxt = head[u];
	head[u] = cnt;
}
void spfa(){
	queue<int> q;
	for(R int i=0;i<=n+1;i++)dis[i] = INF;
	dis[S] = 0; book[S] = 1; q.push(S);
	while(!q.empty()){
		int u = q.front(); book[u] = 0; q.pop();
		for(R int v,w,i = head[u];i;i=edge[i].nxt){
			v = edge[i].v; w = dis[u] + edge[i].w;
			if(dis[v]>w){
				dis[v] = w;
				if(!book[v]){
					book[v]=1; q.push(v);
				}
			} 
		}
	}
}
int main()
{
	n = read();
	m = read();
	for(R int i=0;i<m;i++){
		int u,v,w;
		u = read(); v = read(); w = read();
		add(v,u-1,-w);
	}
	for(R int i=1;i<=n;i++){
		add(i,i-1,0);
		add(i-1,i,1);
	}
	for(R int i=0;i<=n;i++)add(n+1,i,0);
	
	S = n+1;
	
	spfa();
	int mi = INF;
	for(int i=0;i<=n;i++)mi = min(mi,dis[i]);
	printf("%d\n",dis[n]-mi);
	return 0;
 } 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ICPC Asia Shenyang 2019 Dudu's maze

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    用户2965768
  • Codeforces Round 767C 树形结构求子树和

    很容易发现每一颗子树的点权是固定的,因为总和固定,设每一部分的大小为W,那么我们就从下往上更新,遇到等于W的子树就sz重置成0.

    用户2965768
  • Educational Codeforces Round 67 (Rated for Div. 2) A~E 贪心,构造,线段树,树的子树

    Educational Codeforces Round 67 (Rated for Div. 2)

    用户2965768
  • 树上莫队算法

    attack
  • 2017.5.20欢(bei)乐(ju)赛解题报告

    预计分数:100+20+50=first 实际分数:20+0+10=gg 水灾(sliker.cpp/c/pas) 1000MS  64MB 大雨应经下了几天雨...

    attack
  • BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

    Description 一个无向连通图,顶点从1编号到N,边从1编号到M。  小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当...

    attack
  • codeforces329B(bfs)

    由于猎人事先知道我们行走的路线,所以猎人们可以先走到终点前等待,可以使用bfs预处理出终点到各个点之间的距离,如果猎人到终点的距离小于等于我们从起点到终点的距离...

    dejavu1zz
  • Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2) C. Connect(bfs)

    题目链接:http://codeforces.com/contest/1130/problem/C

    Ch_Zaqdt
  • 挑战程序竞赛系列(23):3.2折半枚举

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode 323. 无向图中连通分量的数目(并查集)

    给定编号从 0 到 n-1 的 n 个节点和一个无向边列表(每条边都是一对节点),请编写一个函数来计算无向图中连通分量的数目。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券