正題

---

題目大意

一顆二叉查找樹，以$ke{y}_i$為建值，以$p_i$為價(jià)值。然后一個(gè)節(jié)點(diǎn)的$sum$定義為這棵子樹的價(jià)值之和。

要求相鄰兩個(gè)節(jié)點(diǎn)不互質(zhì)的情況下所有節(jié)點(diǎn)的最大$sum$值之和。

---

解題思路

二叉查找樹滿足中序遍歷的建值從小到大，所以我們考慮區(qū)間$dp$。

每次將兩個(gè)區(qū)間組成的二叉樹合并在一起。

我們預(yù)處理出哪些節(jié)點(diǎn)可以相鄰

設(shè)$f_{0/1,i,j}$表示作為將作為左邊/右邊的子樹與上將上一個(gè)合并過來(根為$i/j$且沒有另一邊子樹)時(shí)的最大價(jià)值。

那么我們可以得出動(dòng)態(tài)轉(zhuǎn)移方程
$$f_{0,i,j}=f_{1,i,k},+f_{0,k+1,j}(v_{i?1,k})$$
$$f_{1,i,j}=f_{1,i,k},+f_{0,k+1,j}(v_{k,j+1})$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=310; struct node{ll k,p; }a[N]; ll n,f[2][N][N],ans,s[N]; bool v[N][N]; bool cmp(node x,node y) {return x.k<y.k;} int main() {//freopen("tree.in","r",stdin);//freopen("tree.out","w",stdout);scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld%lld",&a[i].k,&a[i].p);for(int i=1;i<=300;i++)for(int j=1;j<=300;j++)for(int k=0;k<2;k++)f[k][i][j]=-0x7fffffffffffffll;sort(a+1,a+1+n,cmp);ans=-1e18;for(ll i=1;i<=n;i++)for(ll j=1;j<=n;j++) v[i][j]=(__gcd(a[i].k,a[j].k)==1);for(ll i=1;i<=n;i++){s[i]=s[i-1]+a[i].p;if(i!=1&&!v[i][i-1]) f[0][i][i]=a[i].p;if(i!=n&&!v[i][i+1]) f[1][i][i]=a[i].p;}for(ll l=2;l<=n;l++){for(ll i=1;i<=n-l+1;i++){ll j=i+l-1;for(ll k=i;k<=j;k++){ll b;if(k==i) b=f[0][i+1][j]+(s[j]-s[i-1]);if(k==j) b=f[1][i][j-1]+(s[j]-s[i-1]);if(i<k&&j>k) b=f[1][i][k-1]+f[0][k+1][j]+(s[j]-s[i-1]);if(i!=1&&!v[k][i-1]) f[0][i][j]=max(f[0][i][j],b);if(i!=n&&!v[k][j+1]) f[1][i][j]=max(f[1][i][j],b);if(l==n) ans=max(ans,b);}}}if(ans<0) printf("-1");else printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的jzoj6287-扭动的树【区间dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。