2 条题解
-
0
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define pii pair<int, int> const int N = 1e4 + 5; int n, k; int a[N]; bool dp[N][105]; // dp[i][j] -> 当前做到第i个数 存不存在 sum % k == j 的方案 signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { if (dp[i - 1][j]) // 如果前一位存在 % k == j 那么可以在此基础上继续加当前的数 { int now = (j + a[i]) % k; // 加上 a[i] % k 是多少 dp[i][now] = true; // 更新答案 now = (j - a[i] + k * 10001) % k; // 减去 a[i] % k 是多少 注意: now 应当大于等于0 dp[i][now] = true; // 更新答案 } } } cout << (dp[n][0] ? "YES" : "NO") << endl; // 如果做到第n位时 有 sum % k == 0 则证明存在一种方案 否则不存在 }
信息
- ID
- 415
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 42
- 已通过
- 12
- 上传者