首页 > 代码库 > 1653 种树 2

1653 种树 2

2024-08-13 18:27:27   209人阅读

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


联系
我们