链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191

实现代码：

#include
     
      using namespace std;const int M = 1e5+10;int dp[M];struct node{    int w,v;}lis[M];int main(){    int t,n,m,p,h,c,idx;    cin>>t;    while(t--){        idx = 0;        cin>>n>>m;        memset(dp,0,sizeof(dp));        for(int i = 1;i <= m;i ++){            cin>>p>>h>>c;            int k = 1;            while(c - k>0){                c -= k;                lis[++idx].w = k*h;                lis[idx].v = k*p;                k*=2;            }            lis[++idx].w = c*h;            lis[idx].v = c*p;        }        for(int i = 1;i <= idx;i ++){            for(int j = n;j >= lis[i].v;j --){                dp[j] = max(dp[j],dp[j-lis[i].v]+lis[i].w);            }        }        cout<
      
       <