首页 > 代码库 > 1653 种树 2
1653 种树 2
1653 种树 2
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 Description
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块,并被编号为1…n。每个块的大小为一个单位尺寸并最多可种一裸树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然,b≤e,居民必须保证在指定地区不能种多于地区被分割成块数的树,即要求T≤ e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。
输入描述 Input Description
第一行为n,表示区域的个数;
第二行为h,表示房子的数目;
下面h行描述居民的需要:bet(0<b≤30000,r ≤e-b+ 1)分别用一个空格分开。
输出描述 Output Description
输出为满足所有要求的最少树的数量。
样例输入 Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
【数据规模】
30%的数据满足0<n ≤1000,0<h ≤ 500; 100%的数据满足n ≤30000,h ≤5000。
分类标签 Tags 点此展开
暂无标签
题解:
这是种树3的弱化版
见:http://www.cnblogs.com/shenben/p/5880329.html
AC代码:
#include<cstdio>#include<queue>using namespace std;const int N=5e5+10;struct node{ int v,w,next;}e[N<<2];int n,m,tot,head[N],k[N],dis[N];bool vis[N];inline const int read(){ register int x=0,f=1; register char ch=getchar(); while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}void add(int x,int y,int z){ e[++tot].v=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot;}inline int spfa(){ for(int i=1;i<=n;i++) dis[i]=-0x3f3f3f3f; dis[0]=0; queue<int>q; q.push(0); vis[0]=1; while(!q.empty()){ int h=q.front();q.pop(); vis[h]=0; for(int i=head[h];i;i=e[i].next){ int v=e[i].v,w=e[i].w; if(dis[v]<dis[h]+w){ dis[v]=dis[h]+w; if(!vis[v]){ vis[v]=1; q.push(v); } } } } return dis[n];}int main(){ n=read();m=read(); for(int i=1,a,b,c;i<=m;i++){ a=read()-1;b=read();c=read(); add(a,b,c); } for(int i=1;i<=n;i++){ add(i-1,i,0); add(i,i-1,-1); } printf("%d\n",spfa()); return 0;}
1653 种树 2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。