区间dp-压缩编码

题目大意：

　　给定一段文字，已知单词a₁, a₂, …, a_n出现的频率分别t₁, t₂, …, t_n。可以用01串给这些单词编码，即将每个单词与一个01串对应，使得任何一个单词的编码（对应的01串）不是另一个单词编码的前缀，这种编码称为前缀码。
　　使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为：
　　L=a₁的编码长度×t₁+a₂的编码长度×t₂+…+ a_n的编码长度×t_n。
　　定义一个前缀编码为字典序编码，指对于1 ≤ i < n，a_i的编码（对应的01串）的字典序在a_i+1编码之前，即a₁, a₂, …, a_n的编码是按字典序升序排列的。
　　例如，文字E A E C D E B C C E C B D B E中， 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5，则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11，对应的编码后的01串为1100011011011001010111010011000111，对应的长度L为3×1+3×3+2×4+2×2+2×5=34。
　　在这个例子中，如果使用哈夫曼(Huffman)编码，对应的编码方案是A:000, B:01, C:10, D:001, E:11，虽然最终文字编码后的总长度只有33，但是这个编码不满足字典序编码的性质，比如C的编码的字典序不在D的编码之前。
　　在这个例子中，有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1，编码后的文字长度为35。
　　请找出一个字典序编码，使得文字经过编码后的长度L最小。在输出时，你只需要输出最小的长度L，而不需要输出具体的方案。在上面的例子中，最小的长度L为34。

出题人很良心的说明了用哈夫曼编码的正确性，所以就不能使用哈夫曼树，所以要重新考虑这个问题，题目中的条件是字典序不能变，也就是左边的一定小于右边的字典序所以每次只能合并相邻的两个编码才保证字典序递增，现在的问题就变成了，如何通过合并相邻两个字符使得最终合并完的结果最小，那么就变成了合并石子的板子题，就是区间dp了。

代码：

#include <iostream>
using namespace std;
const int N=1010;
int f[N][N];
int a[N],s[N];
int main(){
    int n;
    cin>>n;
    s[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            f[i][j]=0x3f3f3f3f;
            for(int k=i;k<=j;k++){
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<f[1][n]<<endl;
}

区间dp-压缩编码

原文：https://www.cnblogs.com/kstranger/p/13549955.html