HDU 3033 I love sneakers!(パケットバック変形)

标题链接:Click here~~
タイトル:
n個の物品がK組に分けられ、リュックサックの容量はMであり、各組の物品に少なくとも1個を取り、最大価値を求めることが要求される.
問題解決の考え方:
少なくとも1つ取るので、合法的な状態をマークする方法を考えます.
初期はdp[0][i]を0とし,残りはすべて−1,−1が不正状態を示す.
また、元のリュックサックの2階を循環して位置を変えなければならない.そうしないと、そのグループの1つのものしかリュックサックに入れられない.
trick:データには料金が0のものがあるのでifは位置を交換できません.そうしないと、料金が0のものをリュックサックに2回入れる可能性があります.
コードを书く时1つのkはiを书いて、WAは1时间+、rblを探し终わりました.

#include <stdio.h>
#include <string.h>
#define max(a,b) a > b ? a : b
struct TT
{
    int num,c[101],w[101];
}A[11];
int dp[11][10005];
int main()
{
    int n,V,K,t;
    while(~scanf("%d%d%d",&n,&V,&K))
    {
        memset(A,0,sizeof(A));
        memset(dp,-1,sizeof(dp));
        memset(dp[0],0,sizeof(dp[0]));
        while(n--)
        {
            scanf("%d",&t);
            int &m = A[t].num;
            scanf("%d%d",&A[t].c[m],&A[t].w[m]);
            ++m;
        }
        for(int k=1;k<=K;k++)
            for(int i=0;i<A[k].num;i++)
                for(int j=V;j>=A[k].c[i];j--)
                {
                    if(dp[k][ j-A[k].c[i] ] != -1)
                        dp[k][j] = max(dp[k][j],dp[k][ j-A[k].c[i] ] + A[k].w[i]);
                    if(dp[k-1][ j-A[k].c[i] ] != -1)
                        dp[k][j] = max(dp[k][j],dp[k-1][ j-A[k].c[i] ] + A[k].w[i]);
                }
        if(dp[K][V] < 0)
            puts("Impossible");
        else
            printf("%d
",dp[K][V]);
    }
    return 0;
}