52ms,,,还有更快的吗
#include<iostream>
#include<string.h>
using namespace std;
int f[6010],g[6010];
short q[6010];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
register short v,w,s;
cin>>v>>w>>s;
for(short u=0;u<v;u++){
register short l=0,r=-1;
for(register short k=0;k*v+u<=m;k++){
if(l<=r&&q[l]<k-s)l++;
while(l<=r&&g[u+q[r]*v]<=g[u+k*v]-(k-q[r])*w)r--;
q[++r]=k;
f[u+k*v]=g[u+q[l]*v]+(k-q[l])*w;
}
memcpy(g,f,m*4+4);
}
}
cout<<f[m];
}
里面的short是多余的、、、好像对速度没什么影响
求关注
轻松 $42ms$
可以多跑几次