题目名称 3832. [雅礼集训 2017 Day2] 水箱
输入输出 shuixiang.in/out
难度等级 ★★★☆
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravataryuan 于2023-02-23加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:3, 提交:3, 通过率:100%
Gravataryuan 100 1.206 s 4.63 MiB C++
Gravataryuan 100 1.310 s 4.58 MiB C++
Gravataryuan 100 1.537 s 15.46 MiB C++
本题关联比赛
2022级DP专题练习赛6
关于 水箱 的近10条评论(全部评论)

3832. [雅礼集训 2017 Day2] 水箱

★★★☆   输入文件:shuixiang.in   输出文件:shuixiang.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

给出一个长度为 $n$ 宽度为 $1$ ,高度无限的水箱,有 $n - 1$ 个挡板将其分为 $n$ 个 $1 - 1$ 的小格,然后向每个小格中注水,水如果超过挡板就会溢出到挡板的另一边,这里的水是满足物理定律的(在无挡板阻拦的情况下会向低处流),现在有 $m$ 个条件 ($i$, $y$, $k$) ,表示从左到右数的第 $i$ 个格子中,在高度为 $y + 0.5$ 的地方是否有水, $k = 1$ 表示有水, $k = 0$ 表示没有水,请求出这 $m$ 个条件最多能同时满足多少个条件。本题有多组数据。

【输入格式】

第一行一个正整数 $T$ ,为数据组数。

第二行两个正整数 $n、m$ ,中间用空格隔开。

接下来一行 $n - 1$ 个整数,表示从左到右每一块隔板的高度。

接下来 $m$ 行,每行三个整数 $i 、 y 、 k$ ,表示一个条件。

【输出格式】

共 $T$ 行,每行对应一组数据的答案。

【样例1输入】

2
3 4
3 4
1 3 1
2 1 0
2 2 0
3 3 1
2 2
2
1 2 0
1 2 1

【样例1输出】

3
1

【样例2】

点击下载样例2

【数据规模与约定】

对于 $20\%$ 的数据, $n, m \leq 16$ ;

对于另外 $10\%$ 的数据,只存在指明某处有水的条件;

对于另外 $30\%$ 的数据, $n, m \leq 1000$ ;

对于 $100\%$ 的数据, $n, m \leq 10 ^ 5, T \leq 5$ 。