首页 > itarticle > nwpu2019个人排位赛1c

nwpu2019个人排位赛1c

admin 11月 23, 2020 0

Overview

被这个题关了一整场

题意

有$n$种硬币每种面值$V_i$数量$C_i$，现在要组成面值是$S$的货币，并且每种用到的面值要求使用的数量一样，问方案数。

题解

一开始以为是一个类似多重背包的计数问题，后来发现了要求数量一样，于是就推了一个看起来非常正确的状态：$f_{k,j}$表示每种用$k$枚，组成面值为$j$的方案数。然后就一直没过样例。比赛最后五分钟发现这种状态没办法处理$(2,4)to (2,4,4)$这种转移。

正确的做法是考虑到每种面值数量一样，不妨设为$k$，那么$k|s$，枚举$k$然后修改上界跑01背包即可，好题


#define N 5050
using namespace std;
typedef long long ll;

template <class > inline void read(& x) {
  x = 0; char ch = getchar(); int f = 1;
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
  x *= f;
}

int T, n, s, V[55], C[55];
ll ret, f[N];

inline void _01(int p) {
  memset(f, 0, sizeof(f)); f[0] = 1;
  for (int i = 1; i <= n; ++i) {
    if (C[i] < p) continue;
    for (int j = s / p; j >= V[i]; --j)
      f[j] += f[j - V[i]];
  }
  ret += f[s / p];
}

int main() {
  read(T);
  for (int kase = 1; kase <= T; ++kase) {
    read(s), read(n); ret = 0;
    for (int i = 1; i <= n; ++i) read(V[i]), read(C[i]);
    for (int i = 1; i * i <= s; ++i) {
      if (s % i) continue;
      if (s == i * i) _01(i);
      else _01(s / i), _01(i);
    }
    printf("Case %d: %lldn", kase, ret);
  }
  return 0;
}