2013年4月10日

UVa 11517 - Exact Change


#include <stdio.h>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &m, &n);
    int i, j, p[100], dp[10001] = {1}, cnt[10001];
    for (i = 0; i < n; i++)
      scanf("%d", &p[i]);
    for (i = 0; i <= 10000; i++)
      cnt[i] = 2e9;
    cnt[0] = 0;
    for (i = 0; i < n; i++)
      for (j = 10000; j >= p[i]; j--)
        if (dp[j - p[i]]) {
          dp[j] = 1;
          if (cnt[j] > cnt[j - p[i]] + 1) cnt[j] = cnt[j - p[i]] + 1;
        }
    for (i = m; ; i++)
      if (dp[i]) {
        printf("%d %d\n", i, cnt[i]);
        break;
      }
  }
  return 0;
}

沒有留言:

張貼留言