Codeforces Round #343(Div.2) D. Babaei and Birthday Cake(세그먼트 트리 + 이산화 최적화 DP)
3010 단어 dp세그먼트 트리이산화codeforcesACM-ICPC
제목: n개의 원기둥의 지면 반경과 높이를 제시하고 하나는 책상 위에 직접 놓아야 하며 다른 것은 그 위에 놓아야 한다. 첫 번째는 j개 위에 놓을 수 있는 조건은 다음과 같다. 그리고 i개의 부피가 j개보다 크고 j사고방식: 한눈에 DP이고 상태는 쉽게 나타낼 수 있다. d[i]는 i개까지 얻을 수 있는 최대 총 부피를 나타낸다.max(d[j])+a[i],(ja[j])로 이동.그러나 n은 매우 커서 분명히 최적화해야 한다. 왜냐하면 2층 순환이 하는 일은 i를 만족시키기 전에 a[j]>a[i]를 만족시키는 최대 dp[j]를 찾는 것이다.그러면 두 가지 조건을 동시에 만족시키기 위해 그 중의 한 조건(각 부피)을 라인 트리 하표로 삼아 변형시켜 하나의 조건을 유지할 수 있다. 또한 작은 표는 반드시 정수이고 부피가 너무 크기 때문에 우리는 이산화를 생각했다.그러면 이 문제는 매우 간단하다. 각 부피를 이산화하고 부피를 라인 트리 아래로 표시하여 하나의 구간 최대치를 유지한다. 이 값은 바로 이전에 이미 추가된 dp[j]이다.
자세한 참고 코드:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = int(1e9);
const ll INF64 = ll(1e18);
const int maxn = 100000 + 10;
int T,n,m;
ll d[maxn],b[maxn];
ll maxv[maxn<<2];
struct node {
ll r, h, v;
}a[maxn];
void PushUp(int o) {
maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);
}
void build(int l, int r, int o) {
int m = (l + r) >> 1;
maxv[o] = 0;
if(l == r) return ;
build(l, m, o<<1);
build(m+1, r, o<<1|1);
}
void update(int L, int R, int v, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
if(maxv[o] < d[v]) {
maxv[o] = d[v];
}
return ;
}
if(L <= m) update(L, R, v, l, m, o<<1);
if(m < R) update(L, R, v, m+1, r, o<<1|1);
PushUp(o);
}
ll query(int L, int R, int l, int r, int o) {
int m = (l + r) >> 1;
if(L <= l && r <= R) {
return maxv[o];
}
ll ans = 0;
if(L <= m) ans = max(ans, query(L, R, l, m, o<<1));
if(m < R) ans = max(ans, query(L, R, m+1, r, o<<1|1));
PushUp(o);
return ans;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%I64d%I64d",&a[i].r,&a[i].h);
a[i].v = a[i].r * a[i].r * a[i].h;
b[i] = a[i].v;
}
sort(b+1, b+1+n);
int m = unique(b+1, b+1+n) - b - 1;
build(1, m, 1);
ll cur = 0;
for(int i=1;i<=n;i++) {
int L = lower_bound(b+1, b+1+m, a[i].v) - b;
ll v;
if(L > 1) v = query(1, L-1, 1, m, 1);
else v = 0;
d[i] = (v + a[i].v);
update(L, L, i, 1, m, 1);
cur = max(cur, d[i]);
}
double ans = PI * cur;
printf("%.8f
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백준 알고리즘 14427번 : 수열과 쿼리 15길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.