1904_算法设计例题：图像压缩（DP）

在计算机中常用像素点灰度值序列{ p₁，p₂，…，p_n }表示图像。其中，整数p_i ( 1 ≤ i ≤ n， 1 ≤ n ≤ 100 )表示像素点i的灰度值。通常灰度值的范围是0～255。因此，需要用8位表示一个像素。图像的变位压缩存储格式将所给的像素点序列 { p₁，p₂，...，p_n }分割成m个连续段S₁，S₂，…，S_m。第i个像素段S_i中（ 1 ≤ i ≤ m ），有l[i]个像素，且该段中每个像素都只用b[i]位表示。设t[i]=sum( l[k]，1 ≤ k ≤ i-1 )，i ≤ i ≤ m，则第i个像素段S_i为S_i = { P_t[i]+1，....，P_t[i]+l[i] }，1 ≤ i ≤ m

设hi = log( max(P_k+1，t[i]+1 ≤ k ≤ t[i]+l[i]) )，则hi ≤ b[i] ≤ 8。因此需要用3位表示b[i]，1 ≤ i ≤ m。如果限制1 ≤ l[i] ≤ 255，则需要用8位表示l[i]，1 ≤ i ≤ m。因此，第i个像素段所需的存储空间为l[i]*b[i]+11位。按此格式存储像素序列{p₁，p₂，...，p_n}，需要sum( l[i]*b[i]+11m   i ≤ i ≤ m )。

图像压缩问题要求确定像素序列{ p₁，p₂，…，p_n }的最优分段，使得依此分段所需的存储空间最小。其中，0 ≤ p_i < 256，1 ≤ i ≤ n。每个分段的长度小于256位。

求出最优分段时，所需要的最小存储空间。

输入第一行是单独一个T，代表案例数。接下来每个案例的第一行，是一个n，代表图像像素点的个数。案例第二行，是n个小于256的正整数，表示图像的像素的灰度值。

单独一行，输出所需要的最小存储空间

2
8
1 2 3 4 5 6 7 8
2
10 100

43
25