题解洛谷 P1063 【能量项链】

发布时间:2018-11-24 08:54:16 作者:ex_jason 阅读量:345

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
  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-12-14 20:44:05   ex_jason

我是我吗

 2018-11-24 08:54:16   ex_jason

题解洛谷 P1063 【能量项链...

 2018-11-24 08:53:32   ex_jason

关于NOIP的注意事项?CCF官...

 2018-11-24 08:52:31   ex_jason

最小生成树

 2018-11-22 18:05:09   ex_jason

NOIP2018普及组复赛题解

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

  文章归档

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