分離與合體

題目大意：

有n個區(qū)域，可以把它們分為兩個區(qū)間，結果加上左邊區(qū)間的最左區(qū)域的數(shù)和最右區(qū)域的數(shù)還有右邊區(qū)間的最右區(qū)域的數(shù)，就這樣不停分，使結果最大，并輸出各分界線的位置（按1/2,2/4,4/8的順序）

原題：

題目描述

經(jīng)過在機房里數(shù)日的切磋，LYD從杜神牛那里學會了分離與合體，出關前，杜神牛給了他一個測試…
杜神牛造了n個區(qū)域，它們緊鄰著排成了一行，編號1~n。在這每個區(qū)域里都放著一把OI界的金鑰匙，每一把都有一定的價值，LYD當然想得到它們了。然而杜神牛規(guī)定LYD不可以一下子把它們全部拿走，而是每次只可以拿一個。為了盡快的拿到所有的金鑰匙，LYD自然就用上了剛學的分離與合體特技。
一開始LYD可以選擇從1到n-1的任何一個區(qū)域(記為K)進入，進入后LYD會在K區(qū)域發(fā)生分離，從而分離為兩個小LYD。分離完成的同時會有一面墻在K和K+1區(qū)域之間升起，從而把1到k和k+1到n阻斷為兩個獨立的區(qū)間。然后兩個小LYD分別進入1到k和k+1到n，并在各自的區(qū)間內任選除了區(qū)間末尾區(qū)域以外(即1到k-1或k+1到n-1)的任何一個區(qū)域再次發(fā)生分離，就一共有了4個小小LYD……重復進行以上所敘述的分離，直到每個小LYD發(fā)現(xiàn)自己所在的區(qū)間只剩下了一個區(qū)域，他們就可以抱起自己夢寐以求的OI金鑰匙。
　　但是LYD不能就這么分成n多個個體存在于世界上，這些小LYD還會再合體，合體的兩個小LYD所在的區(qū)間中間的墻會消失。合體會獲得一定的價值，計算方法是：(合并后所在區(qū)間的左右端區(qū)域里金鑰匙的價值之和) 乘 (之前分離的時候所在區(qū)域的金鑰匙價值)。
{例如：LYD曾經(jīng)在1_{3區(qū)間中的2號區(qū)域分離成為1}2和3兩個區(qū)間，合并時獲得的價值就是（1號金鑰匙價值+3號價值）*(2號金鑰匙價值)。}
LYD請你編程求出最終可以獲得的總價值最大是多少。并按照分離階段從前到后，區(qū)域從左向右的順序，輸出發(fā)生分離的區(qū)域編號 (例如：先打印1分為2的分離區(qū)域，然后從左到右打印2分為4的分離區(qū)域，然后是4分為8的…) 。
注意：若有多種方案，選擇分離區(qū)域盡量靠左的方案（也可以理解為輸出字典序最小的）。

輸入

第一行:正整數(shù)n (2<=n<=300)
第二行:n個正整數(shù)，表示1~n區(qū)域里每把金鑰匙的價值。
保證答案及運算過程中不超出longint范圍。

輸出

第一行一個數(shù)，即獲得的最大價值
第二行按照分離階段從前到后，區(qū)域從左向右的順序，輸出發(fā)生分離的區(qū)域編號，中間用一個空格隔開，若有多種方案，選擇分離區(qū)域盡量靠左的方案（也可以理解為輸出字典序最小的）。

輸入樣例

7 1 2 3 4 5 6 7

輸出樣例

238 1 2 3 4 5 6

說明

數(shù)據(jù)范圍約定

對于%20的數(shù)據(jù) N<=10
對于%40的數(shù)據(jù) N<=50
對于%100的數(shù)據(jù) N<=300 a[i]<=300

解題思路：

石子合并改一下，將加上的數(shù)改成題意，然后遞歸輸出分界線

代碼：

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,k,t,a[305],f[305][305],b[305][3055]; void dg(int x,int y,int dep) {if (x>=y) return;//相交在一起了if (dep==k)//剛好{printf("%d ",b[x][y]);//輸出t=1;//記錄return;}dg(x,b[x][y],dep+1);//左邊dg(b[x][y]+1,y,dep+1);//右邊 } int main() {scanf("%d",&n);for (int i=1;i<=n;++i)scanf("%d",&a[i]);for (int i=n-1;i>0;--i)//石子合并模板for (int j=i+1;j<=n;++j)for (int c=i;c<j;++c)if(f[i][c]+f[c+1][j]+(a[i]+a[j])*a[c]>f[i][j])//想加的東西改成最左加最右乘上中間{f[i][j]=f[i][c]+f[c+1][j]+(a[i]+a[j])*a[c];b[i][j]=c;//記錄}printf("%d\n",f[1][n]);t=1;while(t){t=0;//判斷是否有輸出k++;//分的每一層dg(1,n,1);} }

總結

以上是生活随笔為你收集整理的【DP】【递归】分离与合体的全部內容，希望文章能夠幫你解決所遇到的問題。

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