正題

題目鏈接:https://www.ybtoj.com.cn/contest/68/problem/4

---

題目大意

$m$個三元組$(a_i,b_i,c_i)$，如果$c_i\ge min\{x_j\}(a_i\le j\le b_i)$那么可以獲得$min\{x_j\}$的價值，求一個$x$序列使得價值和最大。

---

解題思路

如果根據$x_i$構造一個笛卡爾樹，那么三元組$(a_i,b_i,c_i)$會在$LCA(a_i,b_i)$處產生一次貢獻，考慮用區間$dp$構造笛卡爾樹。

顯然$x_i$肯定是某個$c$，所以先把$c$離散化了

設$f_{l,r,i}$表示已經構造出了$[l,r]$這個范圍的笛卡爾樹，然后目前的根節點權值是$i$時的最大價值和。

然后每次做完處理后綴和，就可以$O(n^{3}m)$實現轉移了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=55,M=4100; int n,m,a[M],b[M],c[M],t[M],cnt[M],tot; int f[N][N][M],g[N][N][M],s[N][N][M],z[N][N][M]; void ct(int l,int r,int k){memset(cnt,0,sizeof(cnt));for(int i=1;i<=m;i++)if(a[i]>=l&&a[i]<=k&&b[i]>=k&&b[i]<=r)cnt[c[i]]++;for(int i=tot;i>=1;i--)cnt[i]+=cnt[i+1];return; } void print(int l,int r,int x){if(!l||!r||l>r)return;x=z[l][r][x];print(l,g[l][r][x]-1,x);printf("%d ",t[x]);print(g[l][r][x]+1,r,x); } int main() {freopen("baddream.in","r",stdin);freopen("baddream.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&a[i],&b[i],&c[i]);t[i]=c[i];}sort(t+1,t+1+m);tot=unique(t+1,t+1+m)-t-1;for(int i=1;i<=m;i++)c[i]=lower_bound(t+1,t+1+tot,c[i])-t;ct(1,n,5);for(int len=1;len<=n;len++){for(int l=1;l<=n;l++){int r=l+len-1;for(int k=l;k<=r;k++){ct(l,r,k);for(int i=1;i<=tot;i++){if(s[l][k-1][i]+s[k+1][r][i]+cnt[i]*t[i]>f[l][r][i]||!f[l][r][i])f[l][r][i]=s[l][k-1][i]+s[k+1][r][i]+cnt[i]*t[i],g[l][r][i]=k;}}for(int i=tot;i>=1;i--){if(s[l][r][i+1]>f[l][r][i])s[l][r][i]=s[l][r][i+1],z[l][r][i]=z[l][r][i+1];else s[l][r][i]=f[l][r][i],z[l][r][i]=i;}}}printf("%d\n",s[1][n][1]);print(1,n,1); }

總結

以上是生活随笔為你收集整理的YbtOJ#20240-[冲刺NOIP2020模拟赛Day10]弱者对决【笛卡尔树,区间dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

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