学步园

裸題

#include<stdio.h>
#include<algorithm>
#include<memory.h>
using namespace std;
int c[111],w[111],num[111];
int dp[111];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&c[i],&w[i],&num[i]);
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++)
        {
            if(c[i]*num[i]>n)//all of the rice can be bought
            {
                //complete pack
                for(int v=c[i];v<=n;v++)
                {
                    dp[v]=max(dp[v],dp[v-c[i]]+w[i]);
                }
            }
            else
            {
                int k=1;
                while(num[i]>k)
                {
                    //01 pack c[i]*=c[i] w[i]*=w[i]
                    for(int v=n;v>=k*c[i];v--)
                    {
                        dp[v]=max(dp[v],dp[v-k*c[i]]+k*w[i]);
                    }
                    num[i]-=k;//rice left
                    k<<=1;
                }
                //consider the rice left
                for(int v=n;v>=num[i]*c[i];v--)
                {
                    dp[v]=max(dp[v],dp[v-num[i]*c[i]]+num[i]*w[i]);
                }
            }
        }//for   pack
        printf("%d\n",dp[n]);
    }//while
    return 0;
}