区间DP

作者: Tsukinousag | 来源:发表于2021-02-22 00:08 被阅读0次

石子合并

原题链接

#include <iostream>
#include <algorithm>

using namespace std;

const int N=310;
const int INF=0x3f3f3f3f;

int n;
int dp[N][N];
int s[N];


int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }
    
    for(int len=2;len<=n;len++)//区间长度是1时合并不需要代价
    {
        for(int i=1;i+len-1<=n;i++)//枚举len下的起点位置
        {
           
            //可以算出终点位置
            int l=i,r=i+len-1;
            
            dp[l][r]=INF;
            for(int k=l;k<r;k++)//枚举分割点k
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
        }
    }
    
    cout<<dp[1][n]<<endl;
    return 0;
}

2.剪绳子

  • 1.dp[i]表示绳子长度为i的最大乘积

  • 2.由于必须切一刀,假设切在j位置,左边长度为j,则右边长度为i-j,对于右边长度,可切可不切

  • 3.dp[i]=max( j * (i-j) ,j * dp[i-j] )

class Solution {
public:
    int maxProductAfterCutting(int length) {
        int dp[length+10];
        memset(dp,0,sizeof dp);
        for(int i=2;i<=length;i++)
        {
            for(int j=1;j<i;j++)
            {
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[length];
    }
};

相关文章

  • 「动态规划」例题之状态和转移方程的设计(2)

    0x50「动态规划」例题 区间DP 线性DP从初态开始,沿着“阶段”向某个方向扩张。而区间DP是线性DP的一种,它...

  • 区间类DP总结

    区间类DP的做法,是用memorized search,把大区间拆分为小区间来解。而dp[i][j] 则直观的表示...

  • 区间DP和回文为主题的DP

    区间DP 区间DP的特征: 可以两个或多个部分进行整合, 或者反过来;能将问题分解为能两两合并的形式.区间DP的求...

  • 区间DP

    区间DP,对于每段小区间,它的最优值是由更小的区间的最优值得出的,由此往下划分,直到单个元素,由他们的组合合并得出...

  • 区间DP

    模板区间dp一般由小区间推出大的区间: http://acm.hdu.edu.cn/showproblem.php...

  • 区间DP

    石子合并 原题链接[https://www.acwing.com/problem/content/284/] 2....

  • DP小结

    DP种类 线性DP 区间DP 树形DP 背包DP01背包满背包完全背包(转成01背包) 例子:线性动规:拦截导弹,...

  • DP模板之---区间DP

    一.经典例题 题目地址: 【P1880】[NOI1995]石子合并 - 洛谷 二.分析 转移方程 dp_max[i...

  • LeetCode 区间dp

    1553. 吃掉 N 个橘子的最少天数 5498. 石子游戏 V

  • 区间dp入门

    题目:洛谷P1040加分二叉树[https://www.luogu.com.cn/problem/P1040]大意...

网友评论

    本文标题:区间DP

    本文链接:https://www.haomeiwen.com/subject/tqncfltx.html