(BOJ)蓄積エネルギー161998回
質問する
https://www.acmicpc.net/problem/16198
に近づく
1.優先キュー
最初は,エネルギーサイズを乗じた順序で並べられた優先キューの作成に近い.最初に作成されたコードは次のとおりです.
コード#コード#
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
public class Main {
static boolean[] isSelected;
static int[] arr; // 값
static int[] left; // 유효한 왼쪽 인덱스
static int[] right; // 유효한 오른쪽 인덱스
static class Node implements Comparable<Node>{
int m;
int l;
int r;
Node (int m, int l, int r) {
this.m = m;
this.l = l;
this.r = r;
}
@Override
public int compareTo(Node o) {
return arr[o.l] * arr[o.r] - arr[this.l] * arr[this.r];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
PriorityQueue<Node> pq = new PriorityQueue<>();
arr = new int[n];
left = new int[n];
right = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(inputs[i]);
}
for (int i = 1; i < n - 1; i++) {
pq.add(new Node(i, i - 1, i + 1));
left[i] = i - 1;
right[i] = i + 1;
}
int sum = 0;
while (!pq.isEmpty()) {
Node node = pq.remove();
int lPt = node.l;
int rPt = node.r;
int mPt = node.m;
// pq에 넣어둔 본인 기준 좌우가 현재 상태에서 본인 기준 좌우가 다르면 건너뛴다.
// (기존에 넣어둔 좌우 중 누군가는 사라졌다는 의미)
if (left[mPt] != lPt || right[mPt] != rPt) {
continue;
}
sum += arr[lPt] * arr[rPt];
if (lPt != 0) {
right[lPt] = right[mPt];
pq.add(new Node(lPt, left[lPt], right[lPt]));
}
if (rPt != n - 1) {
left[rPt] = left[mPt];
pq.add(new Node(rPt, left[rPt], right[rPt]));
}
}
bw.write(Integer.toString(sum));
bw.flush();
bw.close();
}
}
例題はすべて答えを印刷したが、提出すると間違って表示された.よく考えて反例を考える.反例
3
3 1 2 2 3 3
このように、入力値が入ってくると、本人の標準的な2辺の値の積が6の部分になることが多い.この場合、まず入力した中央値を削除しますが、正しいとは保証できません.
DFS
つまり、要するに、すべての人が追及しなければならない.境遇の数はせいぜい2^8-1で、境遇の数はそれぞれ最も値を求めて、もし十分ならば、10まで打つならば、時間内に解決することができます.
コード#コード#
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
public class Main {
static boolean[] isSelected;
static int[] arr; // 값
static int[] left; // 유효한 왼쪽 인덱스
static int[] right; // 유효한 오른쪽 인덱스
static boolean[] isDead;
static int n;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
String[] inputs = br.readLine().split(" ");
arr = new int[n];
left = new int[n];
right = new int[n];
isDead = new boolean[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(inputs[i]);
}
for (int i = 1; i < n - 1; i++) {
left[i] = i - 1;
right[i] = i + 1;
}
dfs(0, 0);
bw.write(Integer.toString(answer));
bw.flush();
bw.close();
}
static void dfs(int depth, int sum) {
if (depth == n - 2) {
if (sum > answer) {
answer = sum;
}
return;
}
for (int i = 1; i < n - 1; i++) {
if (!isDead[i]) {
isDead[i] = true;
int l = left[i];
int r = right[i];
int value = arr[l] * arr[r];
if (l != 0) {
right[l] = right[i];
}
if (r != n - 1) {
left[r] = left[i];
}
// 호출
dfs(depth + 1, sum + value);
right[l] = i;
left[r] = i;
isDead[i] = false;
}
}
}
}
Reference
この問題について((BOJ)蓄積エネルギー161998回), 我々は、より多くの情報をここで見つけました https://velog.io/@jduckling_1024/에너지모으기16198번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol