从0到400000遍历过了,但是我觉得更快的map图应该会更快呀,有点好奇,代码是这样的
TLE代码
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 310; void solve() { int n; cin >> n; int a[N]; for(int i = 0; i < n; i ++ ) cin >> a[i]; unordered_map<int, int> dp; dp[0] = 1; for(int i = n - 1; i >= 0; i -- ) { unordered_map<int, int> dp2; dp2.clear(); for(auto j : dp) { dp2[j.first] = 1; } dp.clear(); for(auto j : dp2) { dp[j.first - a[i]] = 1; dp[j.first + a[i]] = 1; } } int res = 1e9; for(auto j : dp) { res = min(res, abs(j.first)); } cout << res << endl; } signed main() { ios::sync_with_stdio(false), cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while(t -- ) { solve(); } }
AC代码
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 310, M = 400010; void solve() { int n; cin >> n; int a[N]; for(int i = 0; i < n; i ++ ) cin >> a[i]; int dp[M]; memset(dp, 0, sizeof dp); dp[200000] = 1; for(int i = 0; i < n; i ++ ) { int dp2[M]; memcpy(dp2, dp, sizeof dp); memset(dp, 0, sizeof dp); for(int j = 0; j < M; j ++ ) { if(dp2[j] == 1) { dp[j - a[i]] = 1; dp[j + a[i]] = 1; // cout << j - a[i] + 200000 << " " << j + a[i] + 200000 << endl; } } } int res = 1e9; for(int i = 0; i < M; i ++ ) { if(dp[i]) res = min(res, abs(i - 200000)); } cout << res << endl; } signed main() { ios::sync_with_stdio(false), cin.tie(0); cout.tie(0); int t = 1; //cin >> t; while(t -- ) { solve(); } }
全部评论
(0) 回帖