正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1063

---

題目大意

有n個(gè)珠子組成環(huán)，每顆珠子的頭尾標(biāo)記連接，將兩顆珠子合并會產(chǎn)生headi?headj?tailjheadi?headj?tailj的能量，產(chǎn)生一顆頭標(biāo)記為頭珠子的頭標(biāo)記，尾標(biāo)記為尾珠子的尾標(biāo)記。
求所以珠子合并最大能量

---

解題思路

裸的區(qū)間dp

---

code

#include<cstdio> #include<algorithm> using namespace std; int n,h[210],t[210],maxs,f[210][210]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&h[i]); h[i+n]=t[i+n-1]=t[i-1]=h[i]; } t[2*n]=h[1]; for(int i=2;i<=n;i++) for(int l=1;l<=2*n-i+1;l++) { int r=l+i-1; for(int k=l;k<r;k++) { f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]+h[l]*t[k]*t[r]); //動態(tài)轉(zhuǎn)移 } if(i==n) maxs=max(maxs,f[l][r]); } printf("%d",maxs); }

總結(jié)

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

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