← 返回题单
题单练习 动态规划的优化
← 上一题 下一题 →

A7064 | 01串分数最值

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个长度为 $N$、只由 0 和 1 组成的字符串。它的分数按如下规则计算：

对每个区间 $[l_i,r_i]$：
  • 如果在第 $l_i$ 个字符到第 $r_i$ 个字符之间至少出现一个 1，则把 $a_i$ 加到分数中；
  • 否则这个区间对分数贡献为 $0$。
请你求这个字符串分数的最大值。

输入格式

第一行包含两个整数 $N,M$。
接下来 $M$ 行，每行包含三个整数 $l_i,r_i,a_i$。

输出格式

输出一个整数，表示最大可能分数。

输入输出样例

输入 #1
5 3
1 3 10
2 4 -10
3 5 10
输出 #1
20
输入 #2
3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30
输出 #2
90
输入 #3
1 1
1 1 -10
输出 #3
0
输入 #4
1 5
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
1 1 1000000000
输出 #4
5000000000
输入 #5
6 8
5 5 3
1 1 10
1 6 -8
3 6 5
3 4 9
5 5 -2
1 3 -6
4 6 -7
输出 #5
10
C++ 编辑器
输入
输出