单调队列

#include<bits/stdc++.h>
using namespace std;
int w,v,c,n,V,l,r,dp[1001],a[1001],b[1001];
void insert(int x,int y,int a,int b)
{
while(l<=r&&b[r]<=y)
r--;
r++;
a[r]=x;
b[r]=y;
}
int main()
{
scanf("%d%d",&V,&n);
int i,q,d;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&v,&w,&c);
if(!c||V/v<c)
c=V/v;
for(d=0;d<v;d++)
{
l=1;
r=0;
for(q=0;q<=(V-d)/v;q++)
{
insert(q,dp[qv+d]-qw,a,b);
if(a[l]<q-c)l++;
dp[qv+d]=b[l]+qw;
}
}
}
printf("%d\n",dp[V]);
return 0;
}