题目描述:
include[HTML_REMOVED]
using namespace std;
const int N=22222;
int f[N],g[N],q[N];
int main()
{
int n,m;
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i)
{
int v,w,s;
scanf(“%d%d%d”,&v,&w,&s);
memcpy(g,f,sizeof(f));
for(int r=0;r<v;r)
{
int tt=-1,hh=0;
for(int j=r;j<=m;j+=v)
{
while(hh<=tt&&q[hh]<j-sv)
{
hh;
}
while(hh<=tt&&g[q[tt]]-(q[tt]-r)/vw<=g[j]-(j-r)/vw)
{
–tt;
}
q[tt]=j;
f[j]=g[q[hh]]+(j-q[hh])/vw;
}
}
}
cout<<f[m]<<endl;
return 0;
}