题解洛谷 P1063 【能量项链】

发布时间:2018-11-02 18:58:37 作者:ex_jason 阅读量:151

https://www.luogu.org/problem/show?pid=1063 #### 设d[i]表示第i颗珠子头标记,则d[i+1]为尾标记 ; #####设f[i,j]表示从第i颗珠子一直合并到第j堆颗珠子所产生的最大能量,如果这个任务最后一次合并在第k位置,则状态转移方程为 ```cpp [i,j]=max{f[i,k]+ f[k+1,j]+d[i]*d[k+1]*d[j+1]]} , k= i~j-1 ``` #####边界条件:f[i,i]=0 以长度从小到大划分阶段 时间复杂度O(n^3 ) ```cpp //能量项链 #include using namespace std; int n,e[250],f[250][250]={0}; int main() { int i,j,k,mx=0; cin>>n; for (i=1;i<=n;i++) { cin>>e[i]; e[n+i]=e[i]; } for (j=2;j<=2*n-1;j++) for (i=j-1;i>0&&j-i

https://www.luogu.org/problem/show?pid=1063

设d[i]表示第i颗珠子头标记,则d[i+1]为尾标记 ;

设f[i,j]表示从第i颗珠子一直合并到第j堆颗珠子所产生的最大能量,如果这个任务最后一次合并在第k位置,则状态转移方程为
  1. [i,j]=max{f[i,k]+ f[k+1,j]+d[i]*d[k+1]*d[j+1]]} , k= i~j-1
边界条件:f[i,i]=0

以长度从小到大划分阶段

时间复杂度O(n^3 )

  1. //能量项链
  2. #include<iostream>
  3. using namespace std;
  4. int n,e[250],f[250][250]={0};
  5. int main()
  6. {
  7. int i,j,k,mx=0;
  8. cin>>n;
  9. for (i=1;i<=n;i++)
  10. {
  11. cin>>e[i];
  12. e[n+i]=e[i];
  13. }
  14. for (j=2;j<=2*n-1;j++)
  15. for (i=j-1;i>0&&j-i<n;i--)
  16. for (k=i;k<j;k++)
  17. f[i][j]=max(f[i][k]+f[k+1][j]+e[i]*e[k+1]*e[j+1],f[i][j]);
  18. for (i=1;i<=n;i++)
  19. mx=max(mx,f[i][i+n-1]);
  20. cout<<mx<<endl;
  21. return 0;
  22. }

我要评论 登录后才能发布评论

推荐阅读

 2018-11-17 14:31:12   ex_jason

最小生成树

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

 2018-11-10 07:41:45   ex_jason

并查集

 2018-11-10 07:28:04   ex_jason

写代码的小女孩

 2018-11-09 20:18:38   ex_jason

谈谈关于初赛的那些事

 2018-11-09 20:03:06   ex_jason

dijkstra 详解

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.39