Bessie's Birthday Buffet
문제 설명
N개의 목장들이 서로 그래프처럼 연결되어 있고 베시는 목장들 중에서 한 곳에서 시작한다.
여러 목장들을 다니면서 풀을 뜯을 수 있으며 A 목장에서 B 목장으로 이동하는데 걸리는
에너지는 E, 각 목장들에서 풀을 뜯으면 A[i] 에너지를 얻는데, 그러면 더이상 A[i] 이하의
에너지를 얻는 풀을 먹지 않는다고 한다.이 때 베시가 얻을 수 있는 최대 에너지를 구하는 문제해결
Tip
- N 제한 : 1000
- 자기가 먹은 목장들 보다 작은 목장은 가지않는다는 조건
- 풀들의 에너지가 각각 다르다는 점
먼저 각 각각의 목장에서 시작할 경우 다른 목장으로까지 가는데의 간선의 길이를 구한다.
- dist[x][y] = x 에서 y로가는데 걸리는 간선의 길이
점화식
- 만약 에너지가 x인 풀을 먹었을 경우 나는 x보다 큰 풀들을 먹어야 한다.
그렇기 때문에 x보다 큰 풀들에서의 최대 에너지 값들을 알 수 있으면 빠르게
구할 수 있다.
- d[x] = x 목장에 있는 풀을 먹었을 경우 얻을 수 있는 최대 에너지 양
- d[x] = max(d[x], a[x] + dist[x][y] * e + d[y]);
(y = x보다 큰 에너지를 갖고 있는 목장들)코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, e;
ll a[1001], d[1001];
ll dist[1001][1001];
vector<int> v[1001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> e;
vector<pair<int, int>> v2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
v[i].push_back(x);
}
v2.push_back({a[i], i});
}
// dist[x][y] 구하는 과정
queue<pair<int, int>> q;
memset(dist, -1, sizeof(dist));
for (int i = 1; i <= n; i++) {
q.push({i, 0});
dist[i][i] = 0;
while (!q.empty()) {
int x = q.front().first;
int z = q.front().second;
q.pop();
for (int j = 0; j < v[x].size(); j++) {
int y = v[x][j];
if (dist[i][y] != -1) continue;
dist[i][y] = z + 1;
q.push({y, dist[i][y]});
}
}
}
sort(v2.begin(), v2.end());
ll ans = 0;
// d[x] 구하는 과정
for (int i = n - 1; i >= 0; i--) {
int x = v2[i].second;
ll z = v2[i].first;
d[x] = z;
for (int j = i + 1; j < n; j++) {
int nx = v2[j].second;
if (dist[x][nx] != -1)
d[x] = max(d[x], z + d[nx] - dist[x][nx] * e);
}
ans = max(ans, d[x]);
}
cout << ans << '\n';
}Superbull
문제 설명
N개의 팀들이 토너먼트 형식으로 대결을 하는데, 규칙이 존재한다.
- X, Y 두 팀을 고른다. 이 두 팀중에서 1팀을 임의로 선택해 제거할 수 있다.
- X, Y 두 팀이 대결을 할 경우 얻는 점수는 (X XOR Y) 이고, 이를 최대로 만드는게 문제
예를들어, 팀이 3, 6, 9, 10 존재한다고 가정,
- 3, 9 를 선택 후 3 제거, (3 XOR 9) = 10 획득
- 6, 9 를 선택 후 9 제거, (6 XOR 9) = 15 획득
- 6, 10 을 선택 후 9 또는 10제거 (6 XOR 10) = 12 획득
답 : 37
해결
적어도 한 팀은 무조건 경기를 치뤄야 한다.
그러면 각각 경기를 치룰 수 있는 경우를 간선으로 나타내면
- (x, y, z) : x, y가 경기를 치루고 얻는 점수가 z
두 개의 집합으로 나눌 수 있는데,
- A 집합 : 경기를 안한 팀들이 있는 집합
- B 집합 : 경기를 이미 다 한 팀들이 있는 집합
각 간선들을 탐색하면서 다음과 같은 경우로 나눌 수 있다.
1. 두 팀이 A 집합에 있는 경우
- 아직 두 팀 모두 경기를 한번도 안했다는 의미
2. 두 팀이 B 집합에 있는 경우
- 이미 두 팀은 모두 경기를 다 완료했다는 의미
3. 두 팀이 서로 다른 집합에 있는 경우
- 아직 한 팀은 경기를 안했고, 한 팀은 경기를 했지만 승리했다는 것을 의미
위 3가지 경우대로 처리를 하면서 진행하면 해결할 수 있다.
다만, 최대값을 출력해야 하므로 간선을 점수기준으로 내림차순하고 진행 코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[2001];
int p[2001];
struct A {
int x, y;
ll z;
bool operator<(const A obj) {
return z > obj.z;
}
};
vector<A> v;
int find(int x) {
if (p[x] == x)
return x;
else
return p[x] = find(p[x]);
}
void merge(int x, int y) {
x = find(x);
y = find(y);
p[y] = x;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ll dist = a[i] ^ a[j];
v.push_back({i, j, dist});
}
}
sort(v.begin(), v.end());
ll ans = 0;
for (int i = 0; i < v.size(); i++) {
if (find(v[i].x) != find(v[i].y)) {
merge(v[i].x, v[i].y);
ans += v[i].z;
}
}
cout << ans << '\n';
}Cow LineUp
문제 설명
각각 ID를 가지고 있는 소들이 한 줄로 서있고, ID는 중복될 수 있다.
여기서 최대 K개의 ID를 제거했을 경우, 남아있는 소들의 ID들 중 연속으로 같은 ID를
가지는 소들의 최대 길이를 구하는 문제해결
가장 처음에 있는 소는 최대 자신을 포함하여 K + 1개의 다른 ID를가지는 소까지 포함할
수 있다. 즉, K = 1이라고 가정했을 경우, 1, 2, 1, 2, 3 으로 줄 지어 있을 때,
제일 처음에 있는 1번소는 최대 제일 마지막에 있는 2번소까지는 포함시켜도 자신이 정답이
될 수 있다. 왜냐하면 [1, 2, 1, 2] 라고 했을 경우 2를 제거하면 자신만 남을 수 있기
때문이다. 하지만 [1, 2, 1, 2, 3]을 포함시키면 2개를 제거해야하기 때문에 절대 정답이
될 수 없다.
때문에 투 포인터로 l = 0, r = 0으로 두고, r을 한칸씩 증가시키면서 현재 집합에 소들의
ID 값들을 추가시킨다. 만약 ID 값들의 개수가 K + 1 초과하면, 합에 ID 값들의 개수가
K + 1이 될 때까지 l을 증가시킨다.코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
int a[100001];
int c[100001];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
vector<int> v;
for (int i = 1; i <= n; i++) {
cin >> a[i];
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
k += 1;
int ans = 0, cnt = 0, x = 1;
for (int i = 1; i <= n; i++) {
if (c[a[i]] == 0) {
c[a[i]] += 1;
cnt += 1;
while (cnt > k) {
c[a[x]] -= 1;
if (c[a[x]] == 0) cnt -= 1;
x += 1;
}
ans = max(ans, c[a[i]]);
} else {
c[a[i]] += 1;
ans = max(ans, c[a[i]]);
}
}
cout << ans << '\n';
}
Wow