夢に僕らで帆を張って
来るべき日のために夜を超え

标签 区间DP 下的文章

November 2, 2019

洛谷P2466/SDOI2008 Sue的小球

题意略数据范围:$n \le 1000$题解区间$\text{dp}$容易证明,在完成一个区间后处于左/右端点最优由于输入无序,首先按$x$排序,并统计$v$的前缀和以优化计算;另外起始点不一定有球,因此加入起始点用$f[l][r][0/1]$表示已接到区间$[l,r]$的球,现在处于$0$(左端点)/$1$(右端点)失去的最小价值那么区间$[l,r]$由$[l+1,r]$或$[l,r-1]...