Anthony
BAN USERIn C++
#include <bits/stdc++.h>
using namespace std;
const int V = 1000;
bitset<2 * V + 1> can;
int main() {
int n, x;
scanf("%d", &n);
can[0] = 1;
int dist = V, ans = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", &x);
for (int j = 2 * V - x; j >= 0; --j) {
if (can[j]) {
can[j + x] = 1;
if (abs(j + x - V) < dist) {
dist = abs(j + x - V);
ans = j + x;
} else if (abs(j + x - V) == dist) {
ans = max(ans, j + x);
}
}
}
}
printf("%d\n", ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int dp[13][1 << 12];
int x[13], y[13];
int n;
int calc(int p, int mask) {
if (p == 0) return (mask != 0) * 1e9;
int &ret = dp[p][mask];
if (ret != -1) return ret;
ret = 1e9;
for (int i = 0; i <= n; ++i) {
if (mask & (1 << i)) {
int dist = abs(x[p] - x[i]) + abs(y[p] - y[i]);
ret = min(ret, calc(i, mask ^ (1 << i)) + dist);
}
}
return ret;
}
int main() {
for (int i = 0; i < 10; ++i) {
scanf("%d", &n);
scanf("%d %d", &x[n + 1], &y[n + 1]);
scanf("%d %d", &x[0], &y[0]);
for (int j = 1; j <= n; ++j) {
scanf("%d %d", &x[j], &y[j]);
}
memset(dp, -1, sizeof dp);
printf("#%d %d\n", i + 1, calc(n + 1, (1 << (n + 1)) - 1));
}
return 0;
}
Replarrymmapp, Android test engineer at Software AG
Hello, I am name and I live in a city, USA. I am a professional's Podiatric doctor. I am ...
We can also do this with Fenwick Tree.
- Anthony September 03, 2016