UVa : 11450 (Wedding Shopping)

// http://uva.onlinejudge.org/external/114/11450.html
// Runtime: 0.036s
// Tag: Dp

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000005
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

int dr [] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dc [] = {0, 1, 1, 1, 0, -1, -1, -1};

using namespace std;

int amount, garment;
bool memo [20 + 3] [200 + 3];
vector <int> v [20 + 3];
int maxi;

void reset ()
{
    maxi = INF_MIN;

    for ( int i = 0; i < 23; i++ ) {
        for ( int j = 0; j < 203; j++ ) memo [i] [j] = false;
        v [i].clear ();
    }
}

void dp (int at, int sum)
{
    if ( at == garment ) {
        if ( sum <= amount && sum > maxi ) maxi = sum;
        return;
    }
    if ( sum > amount ) return;

    if ( memo [at] [sum] ) return;
    memo [at] [sum] = true;

    for ( size_t i = 0; i < v [at].size (); i++ ) {
        dp (at + 1, sum + v [at] [i]);
    }
}

int main ()
{
    int testCase; scanf ("%d", &testCase);

    while ( testCase-- ) {
        scanf ("%d %d", &amount, &garment);

        reset ();

        for ( int i = 0; i < garment; i++ ) {
            int k; scanf ("%d", &k);
            while ( k-- ) {
                int p; scanf ("%d", &p);
                v [i].push_back (p);
            }
        }

        dp (0, 0);

        if ( maxi == INF_MIN ) printf ("no solution\n");
        else printf ("%d\n", maxi);
    }

	return 0;
}

// @END_OF_SOURCE_CODE

Advertisements