首页 / 算法 / 【算法学习笔记】85.破环为链 序列DP 松弛+代价 SJTU OJ 1073 能量项链

【算法学习笔记】85.破环为链 序列DP 松弛+代价 SJTU OJ 1073 能量项链

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法学习笔记】85.破环为链 序列DP 松弛+代价 SJTU OJ 1073 能量项链，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含700字，纯文字阅读大概需要2分钟。

内容图文

和石子合并很像, 为了对环状进行处理, 我们可以把输入数据复制一份接连在后边. 这样在最后的结果枚举起点找最大即可.

注意这里代价的计算, 因为我们的data[i]只记录了珠子的头珠子的尾部即是下一个珠子的头部.

//因为计算dp[i][j]时需要

用到dp[i][k] k比j小 所以j顺序

dp[k][j] k比i大 所以i逆序 

k插入即可

            for (int i = 2*n-1; i >=1 ; --i){
    for (int j = i; j <= 2*n; ++j){
        dp[i][j] = 0;
        for (int k = i; k < j ; ++k) 
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] +  zz[i]*zz[k+1]*zz[j+1]); 
    }
}

或者用len的方式来遍历 更容易写

            for( int len = 1; len < 2*n; ++len ){
    for (int i = 1; i <= 2*n-len; ++i)
    {
        int j = i + len;
        dp[i][j] = 0;
        for (int k = i; k < j; ++k)
            dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j] + zz[i]*zz[k+1]*zz[j+1]);
    }
}

 

原文：http://www.cnblogs.com/yuchenlin/p/sjtu_oj_1073.html

内容总结

以上是互联网集市为您收集整理的【算法学习笔记】85.破环为链 序列DP 松弛+代价 SJTU OJ 1073 能量项链全部内容，希望文章能够帮你解决【算法学习笔记】85.破环为链 序列DP 松弛+代价 SJTU OJ 1073 能量项链所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1193942.html

来源：【匿名】