洛谷 P1063 能量项链

题目描述

在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。

需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。

例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：

(4⊕1)=10*2*3=60。

这一串项链可以得到最优值的一个聚合顺序所释放的总能量为

((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。

输入输出格式

输入格式：

输入的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i<N< span>时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。

至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。

输出格式：

输出只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量。

输入输出样例

输入样例#1：

4
2 3 5 10

输出样例#1：

说明

NOIP 2006 提高组第一题

注：我是递归的思路，如果你想问递推怎么做，欢迎提问。

这道题呢，感觉与石子合并有些类似，相邻两两合并，每次合并产生一个值，然后求出怎样合并才能使每次合并产生的值和最大。

其实呢，就是划分区间，比如1—4，我就可以枚举成（1,1）（2,4）或（1,2）（3,4）或（1,3）（4,4），当然（2,4）还可以划分为（2,2）（3,4）或（2,3）（4,4），

然后如果当前区间只有一个珠子，那么根本无法合并，返回0，如果当前区间有且只有两个珠子，那么就将两个珠子合并，返回合并后产生的值就行了。

但是这道题还有枚举起点，这应该比较容易看出来，

然后就是关于它是一条链的问题，可以用mod，当然我怕出错，所以多在这后面又多加上了一遍数字，这样万一超了，也不会出错。

 1 #include <iostream>
 2 #include <fstream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 6 using namespace std;
 7 int cnt_beads=0;
 8 int tab_beads[205]={0};
 9 int jiyi[105][105]={0};
10 int dg(int ks,int js);
11 
12 
13 int dg(int ks,int js){
14 if(js>cnt_beads)js%=cnt_beads;
15 if(ks>cnt_beads)ks%=cnt_beads;    
16 if(ks==js)return 0;     
17 if(ks+1==js)return  tab_beads[ks]*tab_beads[js]*tab_beads[js+1];
18 if(ks==cnt_beads&&js==1)return tab_beads[cnt_beads]*tab_beads[1]*tab_beads[2];
19 if(jiyi[ks][js]!=-1)return jiyi[ks][js];
20 int tem=0;
21 int ji=tab_beads[ks]*tab_beads[js+1];
22 for(int x=ks%cnt_beads;x!=js%cnt_beads;x=(x+1)%cnt_beads){
23  if(x==0)x=cnt_beads;
24  tem=max(tem,dg(x+1,js)+dg(ks,x)+ji*tab_beads[x+1]);    
25 }
26 jiyi[ks][js]=tem;
27 return tem;    
28 }
29 
30 
31 int main(int argc, char *argv[]) {
32 cin>>cnt_beads;
33 for(int x=1;x<=cnt_beads;x++)cin>>tab_beads[x];
34 for(int x=cnt_beads+1;x<=cnt_beads*2;x++)tab_beads[x]=tab_beads[x%cnt_beads];
35 
36 int ans=0;
37 for(int x=1;x<=cnt_beads;x++){
38  memset(jiyi,-1,sizeof(jiyi));     
39  ans=max(ans,dg(x,x+cnt_beads-1));    
40 }
41 cout<<ans;
42 
43 return 0;
44 }