「NOIP2018」货币系统

题目链接:LOJ 2951

Solution

一个比较直观的思路就是从小到大排序之后,从小开始往大的扩展,如果如果某某几个数的和等于另外一个数,那么答案就$-1$。
但是这样的做法很显然会超时,考虑类似于完全背包的做法。
$f[i]$表示当前容量为$i$的方案数。
那么转移方程式就是$f[i]=\sum f[i-a[j]]$
一开始的$f[a[i]]=1$
最后所有方案数为$1$的数对答案有$1$的贡献。

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 105;
const int M = 25005;

int n, m;
int a[N];
ll f[M];

int main() {
  freopen("money.in", "r", stdin);
  freopen("money.out", "w", stdout);
  int T;
  scanf("%d", &T);
  while (T--) {
    memset(f, 0, sizeof f);
    m = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      f[a[i]] = 1;
      m = max(m, a[i]);
    }
    for (int i = 0; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (i - a[j] >= 0) {
          f[i] = f[i] + f[i - a[j]];
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
      if (f[a[i]] == 1) 
        ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}
最后修改:2019 年 09 月 07 日 09 : 05 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论