北航算法第三次练习赛

#include <algorithm>
#include <algorithm>
using namespace std;

#define M 1000010
#define N 1000
int v[N],w[N],c[N],f[M],x;

void (int weight,int value){
    for (int j = x;j>=weight;j--)
        f[j] = max(f[j],f[j-weight]+value);
}

void complete(int weight,int value){
    for (int j = weight;j<=x;j++)
        f[j] = max(f[j],f[j-weight]+value);
}

void mutil(int weight,int value,int count){
    int k;
    if(weight*count >=x){
        complete(weight, value);
        return;
    }
    k = 1;
    while(k<count){
        zero(k*weight, k*value);
        count -= k ;
        k*=2;
    }
    zero(weight*count, value*count);
}

int main(){
    int n,num;
    scanf("%d",&n);
    while(n --){
        scanf("%d %d",&x,&num);
        for (int i = 0;i<num;i++)
            scanf("%d %d %d",&v[i],&w[i],&c[i]);
        for (int k = 0;k<num;k++){
            if(c[k] == 233) complete(w[k], v[k]);
            else mutil(w[k], v[k], c[k]);
        }
         printf("%dn",f[x]);
    }
    return 0;
}