种树

题目背景

一条街的一边有几座房子，因为环保原因居民想要在路边种些树。

题目描述

路边的地区被分割成块，并被编号成

1

,

2

,

…

,

n

1, 2, \ldots,n

1,2,…,n。每个部分为一个单位尺寸大小并最多可种一棵树。

每个居民都想在门前种些树，并指定了三个号码

b

b

b，

e

e

e，

t

t

t。这三个数表示该居民想在地区

b

b

b 和

e

e

e 之间（包括

b

b

b 和

e

e

e）种至少

t

t

t 棵树。

居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。

输入格式

输入的第一行是一个整数，代表区域的个数

n

n

n。

输入的第二行是一个整数，代表房子个数

h

h

h。

第

3

3

3 到第

(

h

+

2

)

(h + 2)

(h+2) 行，每行三个整数，第

(

i

+

2

)

(i + 2)

(i+2) 行的整数依次为

b

i

,

e

i

,

t

i

b_i, e_i, t_i

bi​,ei​,ti​，代表第

i

i

i 个居民想在

b

i

b_i

bi​ 和

e

i

e_i

ei​ 之间种至少

t

i

t_i

ti​ 棵树。

输出格式

输出一行一个整数，代表最少的树木个数。

样例 #1

样例输入 #1

9

4

1 4 2

4 6 2

8 9 2

3 5 2

样例输出 #1

5

提示

数据规模与约定

对于

100

%

100\%

100% 的数据，保证：

1

≤

n

≤

3

×

1

0

4

1 \leq n \leq 3 \times 10^4

1≤n≤3×104，

1

≤

h

≤

5

×

1

0

3

1 \leq h \leq 5 \times 10^3

1≤h≤5×103。

1

≤

b

i

≤

e

i

≤

n

1 \leq b_i \leq e_i \leq n

1≤bi​≤ei​≤n，

1

≤

t

i

≤

e

i

−

b

i

+

1

1 \leq t_i \leq e_i - b_i + 1

1≤ti​≤ei​−bi​+1。

#include

using namespace std;

struct aty {

int v,w;

};

vector E[100010];

queue q;

int n,m,dis[100010],u,v,w,fw[100010],op,c,s[100010];

bool vis[100010];

int main() {

scanf("%d%d",&n,&m);

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

scanf("%d%d%d",&u,&v,&w);

E[u-1].push_back({v,w});

}

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

dis[i]=-INT_MAX;

E[i].push_back({i-1,-1});

E[i-1].push_back({i,0});

}

dis[0]=0;

// fw[0]=1;

q.push(0);

while(!q.empty()) {

int u=q.front();

q.pop();

vis[u]=false;

for(int i=0; i

if(dis[u]+E[u][i].w>dis[E[u][i].v]) {

dis[E[u][i].v]=dis[u]+E[u][i].w;

if(!vis[E[u][i].v]) {

q.push(E[u][i].v);

vis[E[u][i].v]=1;

}

}

}

}

printf("%d",dis[n]);

return 0;

}

精彩内容

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。