【題解】UVA 11450 Wedding shopping

#include <iostream>
#include <cstring>
using namespace std;
int T, M, C;
int dp[205][25];
int price[25][25];

int shop(int money, int g){
    if (money < 0) return -1e9;
    if (g == C) return M - money;
    int &ans = dp[money][g];
    if (ans != -1) return ans;
    for (int i = 1; i <= price[g][0]; i++){
        ans = max(ans, shop(money - price[g][i], g+1));
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--){
        cin >> M >> C;
        for (int i = 0; i < C; i++){
            cin >> price[i][0]; // K
            for (int j = 1; j <= price[i][0]; j++){
                cin >> price[i][j];
            }
        }
        memset(dp, -1, sizeof(dp));
        int ans = shop(M, 0);
        if (ans < 0) cout << "no solution\n";
        else cout << ans << "\n";
    }
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T, M, C;
    cin >> T;
    while (T--){
        cin >> M >> C;
        int price[25][25] = {0};
        for (int i = 0; i < C; i++){
            cin >> price[i][0];
            for (int j = 1; j <= price[i][0]; j++){
                cin >> price[i][j];
            }
        }
        bool dp[2][M]; //check whether a state is reachable
        memset(dp, false, sizeof(dp));
        for (int i = 1; i <= price[0][0]; i++){
            if (M - price[0][i] >= 0){
                dp[0][M - price[0][i]] = true;
            }
        }
        int cur = 1, pre = 0;
        for (int g = 1; g < C; g++){
            for (int money = 0; money < M; money++){
                dp[cur][money] = false;
            }
            for (int money = 0; money < M; money++){
                if (dp[pre][money]){
                    for (int i = 1; i <= price[g][0]; i++){
                        if (money - price[g][i] >= 0){
                            dp[cur][money - price[g][i]] = true;
                        }
                    }
                }
            }
            swap(pre, cur);
        }
        int ans = -1;
        for (int i = 0; i < M; i++){
            if (dp[pre][i]){
                ans = i;
                break;
            }
        }
        if (ans >= 0) cout << M - ans << "\n";
        else cout << "no solution\n";
    }
    return 0;
}