1 1 4 6   /*鞋子的数量N[1, 100]; 拥有的金钱M[1, 1w]; 品牌数目[1, 10]*/2 2 5 7   /*以下四行是对于每双鞋的描述*/3 3 4 99  /*品牌种类a; 标价b; 高兴程度增加量c*/4 1 55 775 2 44 666 7 /*每一种品牌的鞋子最少买一双，求最大的高兴程度*/

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 #include <set>10 using namespace std;11 12 //const int = INT_MIN;13 int s[15][105], v[15][105], dp[15][10005];14 15 16 int main () {17     ios :: sync_with_stdio(false);18     int N, M, K, a, b, c;19     while (cin >> N >> M >> K) {20         int cur[15] = {0};21         for (int i = 1; i <= N; ++ i) {22             cin >> a >> b >> c;23             s[a][++ cur[a]] = b;24             v[a][cur[a]] = c;25         }26         /*测试种类*/27 /*28         for (int i = 1; i <= N; ++ i) {29              cout << i << " : " << cur[i] << endl;30         }31 */      /*dp数组初始化*/32         for (int i = 1; i <= K; ++ i) {33             for (int j = 0; j <= M; ++ j) {34                 dp[i][j] = INT_MIN;35             }36         }37 38         for (int i = 1; i <= K; ++ i) {39             for (int j = 1; j <= cur[i]; ++ j) {40                 for (int k = M; k >= s[i][j]; -- k) {41                     dp[i][k] = max (dp[i][k], max (dp[i][k - s[i][j]] + v[i][j], dp[i - 1][k - s[i][j]] + v[i][j]) );42                 }43             }44         }45 46         //cout << dp[K][M] << endl;47         if (dp[K][M] < 0) {48             cout << "Impossible" << endl;49         } else {50             cout << dp[K][M] << endl;51         }52     }53     return 0;54 }