之前一直在luogu博客上

2018年12月25日17:15:52? ? ?copy到博客園

---

?

P1063 能量項鏈

簡單的區間dp

通過解決小區間來影響大區間

環形問題 存儲的時候存兩邊 變成 2*N 個元素

code:

for(int i=1;i<=n;i++) {cin>>e[i];e[i+n]=e[i]; }

s[i][j] ------- i到j的最大能量

k ------------ 左右區間劃分點

把區間分為2個珠子、3個珠子、4個珠子……

s[i][j]=max(s[i][j],左區間能量+右區間能量+合并后的能量)

合并后=左區間第一個珠子右區間第一個珠子總區間最后一個珠子

s[i][j]=max(s[i][j],s[j][k]+s[k+1][i]+e[j]e[k+!]e[j])

Code：

#include<iostream> #include<cstdio> using namespace std; int n; int e[210]; int s[210][210]; int maxn; int main() { cin.sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) { cin>>e[i]; e[i+n]=e[i]; } for(int i=2;i<2*n;i++) { for(int j=i-1;i-j<n&&j>=1;j--) { for(int k=j;k<i;k++) { s[j][i]=max(s[j][i],s[j][k]+s[k+1][i]+e[j]*e[k+1]*e[i+1]); maxn=max(maxn,s[j][i]); } } } cout<<maxn; }

轉載于:https://www.cnblogs.com/_Yrh/p/10175209.html

總結

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

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