P6648 题解 最后更新于 2025-05-02 00:00:33

## 题意 给定一个 $n$ 行的大三角形，其中第 $i$ 行有 $i$ 个数。给定 $k$ ，求所有边长为 $k$ 的子三角形内部几个数的最大值之和。（只算正三角形） $k,n\le 3000$ ## 思路 ST表变式。设 $st[t][i][j]$ 表示以 $(i,j)$ 为顶点，边长为 $t$ 的三角形中所有数的最大值，递推式为： $st[t][i][j]=max\{st[t-1][i][j],\mathop{max}\limits_{x=j}^{j+2^{t-1}}\{st[t-1][i+2^{t-1}][x]\}\}$ 计算答案同理。令 $t$ 为满足 $2^t<k$ 的最大整数， $ans[i][j]$ 表示以 $(i,j)$ 为顶点的三角形的答案，则： $ans[i][j]=max\{st[t][i][j],\mathop{max}\limits_{x=j}^{j+k-2^t}\{st[t][i+k-2^t][x]\}\}$ 然后发现这个东西空间 $O(n^2\log n)$ ，时间 $O(n^3)$ ，寄。 空间问题可以滚动压掉 $t$ 的那一维，变成 $n^2$，安全。 下面那些取 $max$ 值的是连续一段，显然可以单调队列维护，时间也变成 $O(n^2)$ ，安全。 然后做完了。细节一大堆，头一回让我一道蓝交了 20 多发才过。