区间dp

石子合并

问题描述：有多堆石子，排成一排，现将这堆石子合并成有堆，合并的规则是只能是相邻的两堆进行合并，合并所消耗的体力为两堆石子的重量。最后把所以消耗的体力加起来就是合并成一堆所需要的体力，而我们需要求体力的最小值。 问题解决：[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集合表示石子从开始到某一位置的重量和。 注意遍历，初始化

代码语言：javascript复制

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;
}

dp int vector 遍历 集合

0 人点赞