2013年4月9日

UVa 11450 - Wedding shopping


#include <stdio.h>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int m, c, dp[21][200] = {};
    scanf("%d%d", &m, &c);
    int i, j, k, num[21], price[21][20];
    for (i = 1; i <= c; i++) {
      scanf("%d", &num[i]);
      for (j = 0; j < num[i]; j++)
        scanf("%d", &price[i][j]);
    }
    dp[0][0] = 1;
    for (i = 1; i <= c; i++)
      for (j = 0; j < num[i]; j++)
        for (k = price[i][j]; k <= m; k++)
          dp[i][k] += dp[i - 1][k - price[i][j]];
    int max = 0;
    for (i = 0; i <= m; i++)
      if (dp[c][i]) max = i;
    if (max) printf("%d\n", max);
    else puts("no solution");
  }
  return 0;
}

沒有留言:

張貼留言