题目描述

有一个长度为 ( n )、宽度为 1 的水箱，中间有 ( n-1 ) 个挡板将其分成 ( n ) 个 ( 1 \times 1 ) 的小格子。
水超过挡板高度时会溢出到相邻格子，且水会向低处流动。
给定 ( m ) 个条件 ((i, y, k))，表示第 ( i ) 个格子中高度 ( y + 0.5 ) 处是否有水（( k = 1 ) 表示有水，( k = 0 ) 表示没有水）。
要求找出最多能同时满足多少个条件。

条件分析

设第 ( i ) 格的水位为 ( L[i] )（实数）。

• 若 ( k = 1 )，表示 ( y + 0.5 ) 处有水，即： [ L[i] \ge y + 0.5 ]
• 若 ( k = 0 )，表示 ( y + 0.5 ) 处没有水，即： [ L[i] < y + 0.5 ]

水位约束关系

设第 ( i ) 个与第 ( i+1 ) 个格子之间的挡板高度为 ( H[i] )。
根据物理规律，稳定时水位满足：

1. 单调性： [ L[1] \ge L[2] \ge \dots \ge L[n] ] 即水位从左到右单调不增。

2. 挡板限制：

   • 若 ( L[i] > H[i] )，则水会流向右侧，直到 ( L[i] = L[i+1] )（连通）。
   • 若 ( L[i] \le H[i] )，则两格水位独立，只需满足 ( L[i] \ge L[i+1] )。

因此，整个水箱会形成若干个连通块，块内水位相同，且该水位不低于块内所有相邻挡板的高度。

算法思路

1. 离散化

将所有 ( y ) 和 ( y+0.5 ) 的可能取值进行离散化，得到有限个可能的水位值。

2. 预处理

对每个格子 ( i )，计算每个离散水位值 ( v ) 能满足的条件数量 ( \text{cnt}[i][v] )。

3. 动态规划

定义状态： [ dp[i][j] = \text{前 } i \text{ 个格子，第 } i \text{ 个格子水位为离散值 } j \text{ 时，最多满足的条件数} ]

转移时考虑：

• 若 ( L[i] > H[i] )，则 ( L[i+1] = L[i] )（连通）
• 若 ( L[i] \le H[i] )，则 ( L[i+1] \le L[i] )

利用前缀最大值优化，将转移复杂度降为 ( O(1) )。

4. 复杂度优化

• 离散化后水位值数量为 ( O(m) )
• 使用单调性和前缀优化后，总复杂度为 ( O(n \cdot m) )
• 可通过进一步状态合并（连通块 DP）优化

总结

本题的关键在于：

• 将条件转化为水位上下界约束
• 利用水位单调性和挡板连通性建立 DP 模型
• 通过离散化和前缀优化处理大规模数据

最终答案为所有 ( dp[n][j] ) 中的最大值。