TCIRC Judge d088-隔離採礦 解題心得( 題目 )
解題概念:Monotone Stack、PriorityQueue
解題方法:這題很麻煩，首先我們把目前可以繼續接的放在a，a是一個monotone_stack，紀錄越小的高度(這裡指的是兩選定礦坑中間比較高的礦坑高度)則有越高的價值(因為你右邊要放比中間低的)，接著可以之後把他丟進PriorityQueue，pq照高度，直到有比他高的才拿出來，要注意的是我們只要價值比較高的那個，所以不用每個都加到a。總複雜度為O(nlogn)
Java參考程式碼(有更好意見可留言於下方，謝謝!)
//Author:欉恩祁(En Chi Tsung)
//Date:2021/12/22
import java.io.*;
import java.util.*;
public class d088 {
public static int re,ret,mx,ans,idx=0;//idx:紀錄monotone_stack大小
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int[] h=new int[1000005];
public static void main(String[] args) throws Exception{
final int n=orz();//輸入
int v;
pii p;
pii[] a=new pii[1000005];//monotone_stack
a[0]=new pii(1<<30,0);//邊界
PriorityQueue<pii> pq=new PriorityQueue<>(new Comparator<pii>() {
public int compare(pii f,pii s) {
return f.h-s.h;
}
});
for(int i=0;i<n;i++)h[i]=orz();
for(int i=0;i<n;i++) {
v=orz();
mx=-1;
while(!pq.isEmpty()) {
p=pq.poll();
if(p.h>=h[i]) {
pq.offer(p);
break;
}
mx=Math.max(mx,p.v);
}
while(a[idx].h<=h[i]) {
mx=Math.max(mx,a[idx].v);
idx--;
}
mx=Math.max(mx,a[idx].v);
pq.offer(new pii(h[i],a[idx].v+v));
if(a[idx].v<mx)a[++idx]=new pii(h[i],mx);//維護單調性
}
for(int i=0;i<=idx;i++) {
ans=Math.max(a[i].v,ans);
}
while(!pq.isEmpty()) {
ans=Math.max(pq.poll().v,ans);
}
System.out.println(ans);
}
public static int orz()throws Exception {//輸入
ret=0;
re=br.read();
while(re>47&&re<58) {
ret*=10;
ret+=(re&15);
re=br.read();
}
return ret;
}
}
class pii{
int h,v;
pii(int a,int b){
h=a;
v=b;
}
}
文章標籤
全站熱搜
