[每日一题] [NC21228] 货币系统

题目大意：给定n个数字[A1,...,An]，用他们的非负倍数线性组合能生成的集合S[A1,...,An]最少可以由多少个数字生成。比如S[2, 4] = S[2]，只需要一个数字。S[3,5]至少需要两个数字。

https://ac.nowcoder.com/acm/problem/21228

首先猜想需要的个数，就是n减去可以被其他数字表示的数字。一方面，去掉这些数字后，这些数字都可以再被表示出来；另一方面，不是很好证明，但是直觉上是正确的。那么就是需要能知道哪些数字可以被表示出来。当作一个无限背包问题即可。

#define MAXA 25005
int dp[MAXA];

int doit(VI& nums, int n) {
  mem(dp, 0);
  dp[0]=1;
  int cnt = 0;
  REP(i, n) {
    int curr = nums[i];
    if (!dp[curr]) {
      ++cnt;
    }
    REP(j, MAXA) {
      if (j >= curr && dp[j - curr]) {
        dp[j] = 1;
      }
    }
  }
  return cnt;
}

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  FET(t){
    readint(n);
    readvi(nums, n);
    SORT(nums);
    printint(doit(nums, n));
  }
  return 0;
}