1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int n, k, a[110], b[110], c[110]; map<int, int> f[110]; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> b[i]; for (int i = 1; i <= n; i++) c[i] = a[i] - k * b[i]; f[0][0] = 0; for (int i = 0; i < n; i++) { for (auto pi : f[i]) { int j = pi.first; assert(pi.second == f[i][j]); // f[i+1][j] if (f[i+1].find(j) == f[i+1].end()) f[i+1][j] = f[i][j]; else f[i+1][j] = max(f[i+1][j], f[i][j]); // f[i+1][j+c[i]] if (f[i+1].find(j+c[i+1]) == f[i+1].end()) f[i+1][j+c[i+1]] = f[i][j] + a[i+1]; else f[i+1][j+c[i+1]] = max(f[i+1][j+c[i+1]], f[i][j] + a[i+1]); } } if (!f[n][0]) cout << -1 << endl; else cout << f[n][0] << endl; return 0; }
- 1
信息
- ID
- 3
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 6
- 已通过
- 3
- 上传者