本文主要是介绍CF629D Babaei and Birthday Cake，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出N个半径，和高的圆柱，要求后面的体积比前面大的可以堆在前一个的上面，求最大的体积和。
dp[i]=max（dp[j]）+v[i](j<i&&v[i]>v[j]);
离散化，线段树维护区间最大值
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;public class Main {public static void main(String[] args) {new CF_629D().run();}
}class CF_629D {void run() {Scanner cin = new Scanner(new BufferedInputStream(System.in));PrintWriter cout = new PrintWriter(new BufferedOutputStream(System.out));int n = cin.nextInt();for (int i = 0; i < n; i++) {long r = cin.nextLong();volume[i] = r * r * cin.nextLong();}Hash h = new Hash(n, volume);int limit = h.length() - 1;buildtree(1, 0, limit);for (int i = 0; i < n; i++) {int idx = h.Idx(volume[i]);long premax = ask(0, idx - 1, 1, 0, limit);update(idx, premax + volume[i], 1, 0, limit);}cout.printf("%.9f\n", Math.PI * ask(0, limit, 1, 0, limit));cout.flush();}void buildtree(int t, int l, int r) {left[t] = l;right[t] = r;max[t] = 0;if (l == r)return;int mid = (l + r) >> 1;buildtree(t << 1, l, mid);buildtree(t << 1 | 1, mid + 1, r);up(t);}void update(int i, long c, int t, int l, int r) {if (l == r) {max[t] = c;return;}int mid = (l + r) >> 1;if (i <= mid)update(i, c, t << 1, l, mid);elseupdate(i, c, t << 1 | 1, mid + 1, r);up(t);}long ask(int al, int ar, int t, int l, int r) {if (al > ar)return 0L;if (al <= l && r <= ar)return max[t];int mid = (l + r) >> 1;long ans = 0L;if (al <= mid)ans = Math.max(ans, ask(al, ar, t << 1, l, mid));if (ar > mid)ans = Math.max(ans, ask(al, ar, t << 1 | 1, mid + 1, r));return ans;}void up(int t) {max[t] = Math.max(max[t << 1], max[t << 1 | 1]);}final int N = 100_002;long[] volume = new long[N];int[] left = new int[N << 2];int[] right = new int[N << 2];long[] max = new long[N << 2];
}class Hash {Hash(int length, long[] array) {Set<Long> st = new TreeSet<Long>();for (int i = 0; i < length; i++)st.add(array[i]);this.array = new long[st.size()];size = 0;for (long i : st)this.array[size++] = i;}int Idx(long key) {return Arrays.binarySearch(array, 0, size, key);}int length() {return size;}int size;long[] array;
}
这篇关于CF629D Babaei and Birthday Cake的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
