tmp<<=1粗心写成tmp>>=1
居然RE?!没想明白怎么是RE。。。。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int v[110],w[110],c[110],p[1010],ww[1010];
int dp[110];
int main()
{
int T,sum,ans,tmp,r,n;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&sum,&n);
for(int j=0;j<n;j++)
scanf("%d%d%d",&v[j],&w[j],&c[j]);
memset(dp,0,sizeof(dp));
for(int j=0;j<n;j++)
{
if(v[j]*c[j]>=sum)
{
for(int k=v[j];k<=sum;k++)
dp[k]=max(dp[k],dp[k-v[j]]+w[j]);
}
else
{
tmp=1;r=0;
while(c[j]>=tmp)
{
ww[r]=tmp*w[j];
p[r++]=tmp*v[j];
c[j]-=tmp;
tmp<<=1;
}
if(c[j])
{
ww[r]=w[j]*c[j];
p[r++]=v[j]*c[j];
}
for(int k=0;k<r;k++)
{
for(int u=sum;u>=p[k];u--)
dp[u]=max(dp[u],dp[u-p[k]]+ww[k]);
}
}
}
ans=-1;
for(int j=0;j<=sum;j++)
{
if(dp[j]>ans)
ans=dp[j];
}
printf("%d\n",ans);
}
return 0;
}