#1451. 初赛题目-完善15

初赛题目-完善15

(支付问题) 有 n 种纸币,其中第 i 种纸币的面值为 aia_i 元。每种纸币只有一张。求能支付多少种金额(不包括 0 元)。数据范围满足 n≤200, aia_i 的总和不超过 5000。

试补全程序。

1   #include <iostream>
2   
3   using namespace std;
4   
5   const int MAXN = 210;
6   const int MAXM = 5010;
7   int n, m;
8   int f[MAXM], a[MAXN];
9   
10  int main() {
11      cin >> n;
12      for (int i = 1; i <= n; i++) {
13          cin >> a[i];
14          ①;
15      }
16      ②;
17      for (int i = 1; i <= n; i++)
18          ③
19              f[j] = ④;
20      int ans = 0;
21      for (int i = 1; i <= m; i++)
22          if (⑤) ans++;
23      cout << ans;
24      return 0;
25  }
  1. ① 处应填( )。 {{ select(1) }}
  • n += a[i]
  • m += a[i]
  • n = a[i]
  • m = a[i]
  1. ② 处应填( )。 {{ select(2) }}
  • f[0] = 1
  • f[1] = 1
  • a[0] = 1
  • a[1] = 1
  1. ③ 处应填( )。 {{ select(3) }}
  • for (int j = a[i]; j <= n; j++)
  • for (int j = n; j >= a[i]; j--)
  • for (int j = a[i]; j <= m; j++)
  • for (int j = m; j >= a[i]; j--)
  1. ④ 处应填( )。 {{ select(4) }}
  • f[j - 1] + 1
  • f[j - a[i]] + 1
  • f[j] || f[j - a[i]]
  • f[j] && f[j - a[i]]
  1. ⑤ 处应填( )。 {{ select(5) }}
  • f[i]
  • f[i - 1]
  • f[i] == f[i + 1]
  • f[i] == f[i - 1]