Typical DP Contest H-ナップザック

けっこう手こずりました……。
http://tdpc.contest.atcoder.jp/tasks/tdpc_knapsack
　普通のナップザック問題の変形版で、重さの制約に加えて種類の制約があります。合計の重さがW以下、合計の種類がC種類となるように選んだ時の価値の和を最大化せよ、という問題です。
　普通のDP問題が二つくっついただけなのですが、変な解法を使って効率よく計算しないといけません。
　まず
　　dp[i][j] := i種類以下の品物から、重さの和がj以下になるように選んだ時の価値の総和の最大値
とします。
　ある色１～hogeまでを候補としたときのdp[i][j]があります。
　さらにhoge + 1も使う（かもしれない）とき、このテーブルdp[i](0 <= i < c)に対して、fの品物を候補として入れるか入れないかを検討する動的計画法を行います。これによって得られたテーブルtempは、i + 1種類の品物が候補になっているので、dp[i + 1]と比較し大きい方をとっていきます。
　これを繰り返します。

typedef pair<int, int> pint;
int main(){
    int N, W, C;
    vector<pint> products[50];
    cin >> N >> W >> C;
    rep(i, N){
        int w, v, c;
        cin >> w >> v >> c;
        c--;
        products[c].push_back(pint(w, v));
    }
    vector<vector<int>> dp(C + 1, vector<int>(W + 1, 0));
    rep(k, 50){
        for(int i = min(k + 1, C - 1); i >= 0; --i){
            vector<int> temp = dp[i];
            for(pint p : products[k])
              for(int j = W; j >= p.first; --j)
                temp[j] = max(temp[j], temp[j - p.first] + p.second);
            rep(j, W + 1) dp[i + 1][j] = max(dp[i + 1][j], temp[j]);//dp[i][j]より一種類多く使える場合の最大値を更新
        }
    }
    cout << dp[C][W] << endl;
    return 0;
}

　この問題、自力で解けなかったので他の人の解答を参考にしたのですが本当にコレで解けるの感がすごかったです。これを自力で思いつくのはちょっと無理かなあ……。