#4519. Guns N' Roses

题意

二维平面上有若干障碍，每个形如 $(H_i,L_i,R_i,W_i)$, 表示以 $(L_i,H_i)$, $(R_i,H_i)$ 为左右端点、权值为$W_i$ 的线段.

你站在 $(0,0)$. 你可以漫天开枪，若一枪的威力为 $X$，你可以击穿 $W_i\le X$ 的障碍，但子弹会在 $W_i>X$的障碍前停下.

打到端点也算击落.

你要击落所有障碍.

试最小化威力和.
对 $50\%$ 的数据，$n\le 8$.

对 $100\%$ 的数据，$T\le 10$, $1\le n\le 300$, $1\le H_i\le 10^9$, $-10^9\le L_i\le R_i\le 10^9$, $0\le W_i\le 10^9$.

题解

完全不会区间DP啊，考场上连暴力都写挂。。。
显然对障碍先按极角序排序、离散，问题转化为平面上每个高度有一个线段,每次可以从一个横坐标开始射穿这列上的障碍，直到有一个比它大。
对于这样坐标范围不大，点数不多的最优化决策问题，先考虑区间DP，关键在于找到能帮助转移的突破口，使原区间可分为不相互影响的子区间。
发现对于权值最大的障碍，一定要从它包含的坐标中选一个点，发射一个威力为它的枪。又注意到发射完后，所有包含这个点的障碍都会没掉，这样剩下的障碍都分布在这个点的两侧，于是问题转化为两边的相似子问题，就可以区间DP了。