类似'Fence'的思路把,对每一个余数倒序处理,同时用单调队列记录最大值。
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=5005;
inline void qr(int &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
void qw(int x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int f[N],q[N];
int main()
{
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
int n,m;qr(n),qr(m);memset(f,0xcf,sizeof(f));f[0]=0;
for(int i=1;i<=n;i++)
{
int v,w,c;qr(v),qr(w),qr(c);
for(int u=0;u<v;u++)
{
int mxp=(m-u)/v,l=1,r=0;
for(int k=mxp-1;k>=max(mxp-c,0);k--)
{
while(l<=r&&f[u+q[r]*v]-q[r]*w<=f[u+k*v]-k*w)--r;
q[++r]=k;
}
for(int p=mxp;~p;p--)
{
while(l<=r&&p-1<q[l])++l;
if(l<=r)f[u+p*v]=max(f[u+p*v],f[u+q[l]*v]+(p-q[l])*w);
if(p-c-1>=0)
{
int k=p-c-1;
while(l<=r&&f[u+q[r]*v]-q[r]*w<=f[u+k*v]-k*w)--r;
q[++r]=k;
}
}
}
}
int ans=0;
for(int i=1;i<=m;i++)ans=max(ans,f[i]);qw(ans);puts("");
return 0;
}
最后一次更新于2019-10-30
0 条评论