P1063 能量项链
2018-06-17 22:19:54来源:未知 阅读 ()
题目描述
在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),为一个最优聚合顺序所释放的总能量。
输入输出样例
4 2 3 5 10
710
说明
NOIP 2006 提高组 第一题
先拆成环,然后DP
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 void read(int &n) 7 { 8 char c='+';int x=0;bool flag=0; 9 while(c<'0'||c>'9') 10 {c=getchar();if(c=='-')flag=1;} 11 while(c>='0'&&c<='9') 12 {x=x*10+(c-48);c=getchar();} 13 flag==1?n=-x:n=x; 14 } 15 int dp[501][501]; 16 int n; 17 int a[10001]; 18 int main() 19 { 20 read(n); 21 for(int i=1;i<=n;i++) 22 { 23 read(a[i]); 24 a[i+n]=a[i]; 25 } 26 int ans=0; 27 for(int i=n*2;i>=1;i--) 28 { 29 for(int j=i;j<=n*2&&j<n+i;j++) 30 { 31 for(int k=i;k<j;k++) 32 { 33 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[j+1]*a[k+1]); 34 ans=max(ans,dp[i][j]); 35 } 36 } 37 } 38 printf("%d",ans); 39 return 0; 40 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:P1314 聪明的质监员
下一篇:C++类型转换总结
- BZOJ2005: [Noi2010]能量采集(容斥原理 莫比乌斯反演) 2018-07-09
- c语言单项链表学习随笔 2018-06-18
- P1203 [USACO1.1]坏掉的项链Broken Necklace 2018-06-17
- P1972 [SDOI2009]HH的项链 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash