// 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