a bit of dp: SPOJ - SOLDIER

Problem Statement:
SPOJ - SOLDIER

Summary:
There are 6 weapon types, and in total there are \(N<101\) weapons overall. Each weapon has a price and a quality. With money \(T < 1001\), buy a weapon from each weapon type such that the lowest quality amongst the 6 weapon you bought is maximized.

Solution:
This problem is solvable using the similar DP technique in a recent post! It makes use of the small \(T\) space.

Let \(S(k, c)\) be the maximum lowest quality obtainable after buying weapon of type \(1, \ldots, k\) using money less than or equal to \(c\), then we have this relationship:
\(S(k,c) = \max \{ S(k, c-1),  \max_{i \in \text{weapon-k}} \{ q(k,i) + S(k-1,c-p(k,i))\} \} \)

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int dp[7][1005];
int p[7][103], q[7][103], n[7];
/* S(k, c) is the maximum quality using gained after buying k items using cost less or equal to c 
S(k, c) = max { min(q[k][i], S(k-1, c-p[k][i])) , S(k, c-1) }
*/
int main(){
    int N, t;
    cin >> N >> t;
    for(int i=0;i<7;++i){
        n[i] = 0;
        for(int j=0;j<1005;++j){
            dp[i][j] = 0;
        }
    }
    for(int i=0;i<N;++i){
        int u,v,w;
        cin >> u >> v >> w;
        p[u][n[u]] = v;
        q[u][n[u]] = w;
        n[u]++;
    }
    for(int i=0;i<=t;++i){
        dp[0][i] = (int) 1e9;
    }
    for(int k = 1; k <= 6; ++k){
        for(int c = 1; c<=t; ++c){
            dp[k][c] = dp[k][c-1];
            for(int i=0;i<n[k];++i){
                if( c - p[k][i] < 0 ) continue;
                dp[k][c] = max(dp[k][c], min(q[k][i], dp[k-1][c - p[k][i]]));
            }
        }
    }
    cout << dp[6][t] << endl;
    return 0;
}