题解：P7084 [NWRRC2013] Flight Boarding Optimization

· · 题解

题意

# 分析： 既然有 $k$ 段这个限制，那么采用 DP 的时候必然需要将 $k$ 作为一个状态：所以状态表示为 $dp_{i,j}$，以 $i$ 为分段的最后一个数字，一共 $j$ 段的答案。因为状态转移一定是 $dp_{i,j}\to dp_{k,j+1}$，所以将第二维优化。状态转移的时候，需要求一下在 $[i+1,j]$ 区间内的正序对个数，这个可以预处理解决：对于一个正序对 $x-y$，在二维坐标中将 $(x,y)$ 值加一。最后求得时候，其实就是要 $x$ 和 $y$ 均在给定的区间内的正序对个数，就是在一个正方形内的点的个数，预处理出每个点到原点的矩形中点的个数即可。