暑假acwing算法总结32:区间DP

  • 2、类似Huffman树的石子合并

  • Huffman树是所有任意两堆石子可以任意合并,但是该DP问题只能合并相邻的两堆,所以用区间DP
  • 按照区间长度遍历,先遍历两堆的最小值显然是所有相邻两堆相加,遍历三堆及以上时就要考虑那种更优,通过从l~r-1划线的方式找最优的解,前提是前面的状态已经被计算过
  • 像1 3 5
  • 前面的状态f(1,2)=4,f(2,3)=8
  • 所以在1~2划线f(1,3)=min(f(1,1)+f(2,3),f(1,2)+f(3,3))
  • 同理最终状态f(1,n)就是最小值
  • 代码
#include<iostream>
using namespace std;
const int N=310;
int f[N][N];
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int l=i,r=i+len-1;
            f[l][r]=2e9;
            for(int k=l;k<r;k++)
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+a[r]-a[l-1]);
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}
  • 2021-08-02写于商丘

上一篇:电文的编码与编译


下一篇:Huffman编/译码器