ABC219 H
跟关路灯很像。
很容易注意到我们拿走的只能是一个区间，观察n的范围发现区间dp是个好想法。
朴素的想法是定义 \(f_{i,j,k,0/1}\) 为拿走i到j里面的所有数，走了k秒，现在在 i/j 的方案数。
然后发现k太大了。
咱当时的想法是希望优化复杂度，把k去掉结果发现不能保证正确性。
参照关路灯。
把费用提前计算。也就是然后走k步会收到（剩下还没吃的）*k的伤害。
结果你发现不一定所有的都吃的到，降到0就拿不到了。怎么办呢？
那就把你接下来要拿走的数量加入方程反正多个n也不会炸啊嗯。
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N=305;
int n,m,f[N][N][N][2];
struct node{
int name,data;
}a[N];
bool cmp(node x,node y){
return x.name<y.name;
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].name,&a[i].data);
a[++n]={0,0};
sort(a+1,a+1+n,cmp);
memset(f,-0x3f,sizeof(f));
for(int i=1;i<=n;i++)for(int j=0;j<=n;j++)if(a[i].name==0&&a[i].data==0)f[i][i][j][0]=f[i][i][j][1]=0;
int ans=0;
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=1;k<=n;k++){
f[i][j][k][0]=max(f[i+1][j][k][0]-(k-1)*(a[i+1].name-a[i].name),f[i+1][j][k][1]-(k-1)*(a[j].name-a[i].name));
f[i][j][k][0]=max(f[i][j][k][0],max(f[i+1][j][k+1][0]-k*(a[i+1].name-a[i].name)+a[i].data,f[i+1][j][k+1][1]-k*(a[j].name-a[i].name)+a[i].data));
f[i][j][k][1]=max(f[i][j-1][k][0]-(k-1)*(a[j].name-a[i].name),f[i][j-1][k][1]-(k-1)*(a[j].name-a[j-1].name));
f[i][j][k][1]=max(f[i][j][k][1],max(f[i][j-1][k+1][0]-k*(a[j].name-a[i].name)+a[j].data,f[i][j-1][k+1][1]-k*(a[j].name-a[j-1].name)+a[j].data));
ans=max(ans,max(f[i][j][k][1],f[i][j][k][0]));
}
}
}
printf("%lld\n",ans);
return 0;
}