1 条题解

  • 0
    @ 2024-8-29 21:02:35
    #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
    上传者