bzoj 3928 4048 [Cerc2014] Outer space invaders

Posted by

[TOC]

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=4048

题解

双倍经验吼啊!
首先发现坐标蛮大的,但是$n\leq 300 $,于是我们可以离散化一下。
区间DP:设$ f[i][j] $表示把起点为$ j $,长度为$ i $的区间里的外星人都打死的最小花费。
每次转移时,在区间里找到最远的外星人$ x $。
状态转移方程:
$$ f[i][j]=min{f[k-j+1][j]+f[j+i-k][k]+d[x]},\quad a[x]\leq k\leq b[x] $$
答案为$ f[m][0] $,$ m $为离散化之后的最大区间坐标。
(用开区间转移的时候似乎更容易处理一点)

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注