一、题目
数轴上有 (n) 个蜡烛，第 (i) 个蜡烛的坐标是 (x_i)，长度时 (a_i)，每一秒蜡烛会减少 (1) 的长度（到 (0) 为止），每秒你可以移动一个单位长度，你可以把位置上的蜡烛吹熄（停止减少长度），问最后剩下的蜡烛总长度最大值。
(nleq 300)
二、解法
因为我们无法记录时间，所以我们无法知道蜡烛的具体长度，但是我们知道每一秒蜡烛会减少 (1) 的长度，所以应用费用提前计算的思想，我们可以计算有多少个以后吹熄的蜡烛受到了这次减少的影响。
发现走的过程是一个区间，所以可以往区间 (dp) 方向想，每次扩展左右端点即可。因为要计算贡献我们可以额外记录还要访问的蜡烛的个数，那么每次新走到一个点时决策选不选它即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 305;
#define int long long
const int inf = 1e18;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,ans,dp[M][M][M][2];
struct node
{
int x,y;
bool operator < (const node &b) const
{
return x<b.x;
}
}s[M];
void upd(int &x,int y) {x=max(x,y);}
signed main()
{
n=read();
for(int i=1;i<=n;i++)
s[i].x=read(),s[i].y=read();
s[++n].x=0;s[n].y=0;
sort(s+1,s+1+n);ans=-inf;
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++)
{
if(s[i].x==0 && s[i].y==0)
{
for(int j=0;j<=n;j++)
dp[i][i][j][0]=0;
}
}
for(int i=n;i>=1;i--)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++)
{
upd(dp[i][j][k][0],dp[i][j][k][1]-(s[j].x-s[i].x)*k);
upd(dp[i][j][k][1],dp[i][j][k][0]-(s[j].x-s[i].x)*k);
int cr=(s[j+1].x-s[j].x)*k,cl=(s[i].x-s[i-1].x)*k;
if(j<n) upd(dp[i][j+1][k-1][1],dp[i][j][k][1]-cr+s[j+1].y);
if(j<n) upd(dp[i][j+1][k][1],dp[i][j][k][1]-cr);
if(i>1) upd(dp[i-1][j][k-1][0],dp[i][j][k][0]-cl+s[i-1].y);
if(i>1) upd(dp[i-1][j][k][0],dp[i][j][k][0]-cl);
}
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int l=0;l<2;l++)
upd(ans,dp[i][j][0][l]);
printf("%lld
",ans);
}