題目鏈接：點擊查看

題目大意：給出 $n$ 個建筑，每個建筑有一個高度和一個美麗值，現(xiàn)在要求劃分為數(shù)個連續(xù)的區(qū)間，使得所有區(qū)間的貢獻之和最大，其中每個區(qū)間的貢獻值為，區(qū)間中高度最低的建筑物的美麗值

題目分析：不難分析出一個很簡單的經典區(qū)間劃分 $dp$，時間復雜度是 $O(n^2)$ 的：

$d{p}_i=max(d{p}_j+val(j+1,i))$，其中 $j\in [0,i?1]$

$val(l,r)$ 代表的是 $[l,r]$ 作為一段區(qū)間的貢獻，也就是高度最小值位置的美麗值

一開始感覺是直接將 $dp+val$ 扔進線段樹然后每次 $log(n)$ 轉移，但是卡在了插入一個新點后更新前面所有 $val$ 的操作，看了題解后發(fā)現(xiàn)是可以直接在單調棧彈棧的時候維護答案，感覺這個模型確實蠻經典的樣子

就比如用單調棧維護一個單調遞增的序列，在需要插入第 $i$ 個點的時候，因為需要維護單調棧，所以大于 $h_i$ 的點都需要被彈掉

考慮被彈出去的點 $st[top]$ 和棧頂前面的一個點 $st[top?1]$，正因為滿足了 $h_{st[top]}>h_{st[top?1]}$，原本 $j\in [st[top?1],i?1]$ 的區(qū)間 $val(j+1,i)$ 的值為 $a_{st[top]}$。因為大于 $h_{st[top]}$ 的點都已經被 $st[top]$ 彈出去了，所以到目前為止 $h_{st[top]}$ 一定是區(qū)間 $[st[top?1]+1,i]$ 這段區(qū)間中的最小值了

繼續(xù)上述的論證，當 $st[top]$ 被彈出去后，點 $i$ 一定是需要進棧的，就目前而言，此時 $j\in [st[top?1],i?1]$ 的區(qū)間 $val(j+1,i)$ 從 $h_{st[top]}$ 變成了 $h_i$

上面兩段就是在插入點 $i$ 時更新線段樹的操作，最后答案顯然就是區(qū)間詢問 $[0,i?1]$ 中的最大值了

每個點都會入棧一次，至多出棧一次，線段樹每次操作是 $log(n)$ 的，所以時間復雜度是 $O(nlogn)$

代碼：

// Problem: E. Skyline Photo // Contest: Codeforces - Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round) // URL: https://codeforces.com/contest/1484/problem/E // Memory Limit: 256 MB // Time Limit: 2500 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const LL inf=0x3f3f3f3f3f3f3f3f; const int N=1e6+100; int h[N],a[N]; LL dp[N]; struct Node {int l,r;LL mmax,lazy; }tree[N<<2]; void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); } void pushdown(int k) {if(tree[k].lazy) {LL lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].mmax+=lz;tree[k<<1|1].mmax+=lz;tree[k<<1].lazy+=lz;tree[k<<1|1].lazy+=lz;} } void build(int k,int l,int r) {tree[k]={l,r,-inf,0};if(l==r) {return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void update(int k,int pos,LL val) {if(tree[k].l==tree[k].r) {tree[k].mmax=val;return;}pushdown(k);int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) {update(k<<1,pos,val);} else {update(k<<1|1,pos,val);}pushup(k); } void update(int k,int l,int r,LL val) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].mmax+=val;tree[k].lazy+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); } LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return -inf;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].mmax;}pushdown(k);return max(query(k<<1,l,r),query(k<<1|1,l,r)); } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) {read(h[i]);}for(int i=1;i<=n;i++) {read(a[i]);}build(1,0,n);update(1,0,0);stack<int>st;st.push(0);for(int i=1;i<=n;i++) {while(st.size()&&h[st.top()]>h[i]) {int pre=st.top();st.pop();update(1,st.top(),pre-1,-a[pre]);}update(1,st.top(),i-1,a[i]);dp[i]=query(1,0,i-1);update(1,i,dp[i]);st.push(i);}cout<<dp[n]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1484E Skyline Photo(dp+单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。