a数组的元素无论加减b元素,a的原数不变,先对a数组求和 再从b中挑取0-n个元素即可。
为什么开205的数组?因为b中几个数的算术和可能为负,即所有算术和在(-100,100)范围。
#include <bits stdc++.h> using namespace std; typedef long long ll; bool dp[205], ex[205]; int main() { int i, j, n, y, a, b, sum; cin >> n >> y; for (i = sum = 0; i < n; i++) { cin >> a; sum = (sum + a) % y; } dp[sum + 100] = true; while (n--) { for (i = 0; i < 205; i++) { ex[i] = dp[i]; } cin >> b; for (j = 0; j < 205; j++) { if (ex[j]) { dp[(j - 100 + b) % y + 100] = true; dp[(j - 100 - b) % y + 100] = true; } } } for (i = 204; i >= 100; i--) { if (dp[i]) { cout << i - 100 << endl; break; } } system("pause"); return 0; }