区间dp

code-child

发布于 2023-05-30 11:20:37

7760

文章被收录于专栏：codechildcodechild

石子合并

问题描述：有多堆石子，排成一排，现将这堆石子合并成有堆，合并的规则是只能是相邻的两堆进行合并，合并所消耗的体力为两堆石子的重量。最后把所以消耗的体力加起来就是合并成一堆所需要的体力，而我们需要求体力的最小值。问题解决：[i][j]表示从第i堆到第j堆的合并的集合，f[i][j]表示第i堆到第j堆合并的体力最小值。这个集合怎么枚举表示呢？当然是把区间进行分割：下面列举分割 i,[i+1，j] [i,i+1],[i+2,j] '''''' [i,i+k],[i+k+1,j] k>=0&&k<j-i 怎么求f[i][j]呢？就是上面的最小体力值。下面是求f[i][j]=min(f[i][i+k]+f[i+k+1][j]+s[j]-s[i-1]),s集合表示石子从开始到某一位置的重量和。注意遍历，初始化

cpp#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> v(n+1),s(n+1);
    
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        s[i]=s[i-1]+v[i];
    }
    
    vector<vector<int>> f(n+1,vector<int>(n+1));
    
    for(int len=2;len<=n;len++)//长度为1的都是0，不需要从1开始遍历
    {
        for(int left=1;left+len-1<=n;left++)//从1开始生成长度为len的区间；并且不断更新区间——滑动区间。
        {
            int right=left+len-1;
            f[left][right]=2e10;//设成最大值，表示不能合并
            for(int k=0;k<right-left;k++)
            f[left][right]=min(f[left][right],f[left][left+k]+f[left+k+1][right]+s[right]-s[left-1]);
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除