AtCoder Beginner Contest 219 H
假设我们按照蜡烛的坐标从小到大排序，那么我们每到达一个蜡烛，肯定要熄灭它。
所以，在任意时刻我们走过的蜡烛都是一个区间。
按坐标正负分成\(2\)部分，分别按到\(0\)的距离排序。我们设\(dp(l,r,0/1)\)表示熄灭了负数坐标蜡烛的前\(l\)个，正数坐标的前\(r\)个，当前在最左侧还是最右侧。
转移就可以枚举下一次走到负数坐标的\(l+1\)项还是整数坐标的\(r+1\)项。
但有一个问题：\(dp(l,r,0/1)\)是维护时间，还是维护目前熄灭蜡烛的最大长度？
发现两者一个最优，另一个未必最优。我们将任何一个放入\(dp\)中代表一个维度，此时就可以了，但状态数太大了。
有\(2\)种解决方案。
我们设\(state.time\)表示方案\(state\)所需的时间，\(state.length\)表示目前熄灭蜡烛的长度和。
我们一个\(dp\)中的元素可以存若干个状态，但是若存在状态\(x,y\)，使得\(x.time
然而这样剩余的状态还是太多。考虑使用剪枝，具体的，若存在状态\(x,y\)，若\(y.length-n(y.time-x.time)>x.length\)，则\(x\)可以不要。
时间复杂度玄学，不过是很快的，比\(O(n^3)\)还要优秀。
第二种方案：我们发现可以维护\(dp(l,r,k,0/1)\)，\(l,r,0/1\)和之前的一样，而\(k\)的意思是，我们在剩下的蜡烛中还有\(k\)个是在燃烧完被熄灭的。
那么转移的时候，假设到下一个所花费的时间是\(t\)，那么在\(t\)时间内，这\(k\)个蜡烛的长度都会减\(1\)，故这\(k\)个蜡烛的长度共减去了\(kt\)。到下一个蜡烛时，我们有\(2\)种选择：它在这\(k\)个蜡烛中，则将\(dp(l,r,k,p)+len\)转移到\(dp(l',r',k-1,p')\)，否则将\(dp(l,r,k,p)\)转移到\(dp(l',r',k,p')\)。
那么有一个问题，万一这\(k\)个蜡烛中有的燃烧成了负数呢？
可以发现，若\(dp(l,r,k,p)\)中有蜡烛燃烧成负数，那就会对答案造成一个负的贡献，不妨抛掉这些蜡烛，也就是取\(dp(l,r,k-1,p)\)会更优，所以不必考虑。
时间复杂度为\(O(n^3)\)。
#include
using ll=long long;
const int maxn=305;
int n,m1,m2;
ll f[maxn][maxn][maxn][2];
bool vis[maxn][maxn][maxn][2];
std::pair a[maxn],b[maxn];
ll dfs(int l,int r,int k,int where) {
if(k==0) return 0;
if(vis[l][r][k][where]) return f[l][r][k][where];
ll &ret=f[l][r][k][where]; ret=-1e18;
vis[l][r][k][where]=1;
ll now,nxt;
if(where==0) now=a[l].first;
else now=b[r].first;
for(int i=0;i<2;i++) {
int l_=l,r_=r,len;
if(i==0) nxt=a[l+1].first,len=a[l+1].second,l_++;
else nxt=b[r+1].first,len=b[r+1].second,r_++;
ll dis=abs(now-nxt);
if(l_>m1||r_>m2) continue;
ret=std::max(ret,dfs(l_,r_,k,i)-k*dis);
ret=std::max(ret,dfs(l_,r_,k-1,i)+len-k*dis);
}
return ret;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
ll ix,ia;
scanf("%lld%lld",&ix,&ia);
if(ix<0) a[++m1]=std::make_pair(ix,ia);
else b[++m2]=std::make_pair(ix,ia);
}
a[0]=std::make_pair(0ll,0ll),b[0]=std::make_pair(0ll,0ll);
std::sort(a+1,a+m1+1,std::greater>());
std::sort(b+1,b+m2+1);
ll ans=0;
for(int i=1;i<=n;i++)
ans=std::max(ans,dfs(0,0,i,0));
printf("%lld\n",ans);
return 0;
}