ccf-圧縮符号化
2803 ワード
原題:
問題の説明
試験問題番号:
201612-4
試験問題名:
あっしゅくコーディング
時間制限:
3.0s
メモリの制限:
256.0MB
問題の説明:
問題の説明
文字、既知の単語aを指定
1, a
2, …, a
n出現頻度それぞれt
1, t
2, …, t
n.各単語が1つの01列に対応するように、これらの単語を01列で符号化することができ、いずれの単語の符号化(対応する01列)も別の単語で符号化されたプレフィックスではなく、この符号化をプレフィックス符号と呼ぶ.
プレフィックスコードを使用して文字を符号化することは、その文字の各単語を順番に符号化することを意味する.接頭辞で符号化されたテキストの長さは、次のとおりです.
L=a
1の符号化長×t
1+a
2の符号化長×t
2+…+ a
nの符号化長×t
n.
接頭辞符号化を辞書シーケンス符号化として定義し、1≦iiの符号化(対応する01列)の辞書順はa
i
+1符号化前、すなわちa
1, a
2, …, 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である場合、1つの実行可能な符号化スキームは、A:000,B:001,C:01,D:10,E:11であり、対応する符号化後の01列は110001011011011001011101001001001000111であり、対応する長さLは3である×1+3×3+2×4+2×2+2×5=34.
この例では、ハフマン符号化を用いる場合、対応する符号化方式はA:00、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である.
入力フォーマット
入力された最初の行には、単語の数を表す整数nが含まれます.
2行目はn個の整数を含み、aをそれぞれスペースで区切る
1, a
2, …, a
n出現頻度、すなわちt
1, t
2, …, t
n.注意してくださいa
1, a
2, …, a
n具体的にどんな単語が本題の解に影響しないのでaを入力しない
1, a
2, …, a
n.
出力フォーマット
文字が符号化された長さLの最小値を示す整数を出力する.
サンプル入力
5
1 3 4 2 5
サンプル出力
34
サンプルの説明
この例が問題記述の例である.35を手に入れた場合、計算に問題があることを説明します.サンプル出力が間違っていると疑わないで、自分のアルゴリズムを自分でチェックしてください.
評価用例の規模と約束
30%の評価例について、1≦n≦10、1≦t
i ≤ 20;
60%の評価例について、1≦n≦100、1≦t
i ≤ 100;
100%の評価例について、1≦n≦1000、1≦t
i ≤ 10000.
分析:
石類問題を統合し、動的に計画する.
元のアルゴリズムはdp[n][n]を構築し,n−1からnまでのマージの最小値,n−2からnまでのマージの最小値,,,1からnまでのマージの最小値を後から順に求める.dp[1][n]が答えです.
ここでは、平行四角形の最適化が必要です.最適化後のコードは次のとおりです.
コード:
問題の説明
試験問題番号:
201612-4
試験問題名:
あっしゅくコーディング
時間制限:
3.0s
メモリの制限:
256.0MB
問題の説明:
問題の説明
文字、既知の単語aを指定
1, a
2, …, a
n出現頻度それぞれt
1, t
2, …, t
n.各単語が1つの01列に対応するように、これらの単語を01列で符号化することができ、いずれの単語の符号化(対応する01列)も別の単語で符号化されたプレフィックスではなく、この符号化をプレフィックス符号と呼ぶ.
プレフィックスコードを使用して文字を符号化することは、その文字の各単語を順番に符号化することを意味する.接頭辞で符号化されたテキストの長さは、次のとおりです.
L=a
1の符号化長×t
1+a
2の符号化長×t
2+…+ a
nの符号化長×t
n.
接頭辞符号化を辞書シーケンス符号化として定義し、1≦i
i
+1符号化前、すなわちa
1, a
2, …, 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である場合、1つの実行可能な符号化スキームは、A:000,B:001,C:01,D:10,E:11であり、対応する符号化後の01列は110001011011011001011101001001001000111であり、対応する長さLは3である×1+3×3+2×4+2×2+2×5=34.
この例では、ハフマン符号化を用いる場合、対応する符号化方式はA:00、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である.
入力フォーマット
入力された最初の行には、単語の数を表す整数nが含まれます.
2行目はn個の整数を含み、aをそれぞれスペースで区切る
1, a
2, …, a
n出現頻度、すなわちt
1, t
2, …, t
n.注意してくださいa
1, a
2, …, a
n具体的にどんな単語が本題の解に影響しないのでaを入力しない
1, a
2, …, a
n.
出力フォーマット
文字が符号化された長さLの最小値を示す整数を出力する.
サンプル入力
5
1 3 4 2 5
サンプル出力
34
サンプルの説明
この例が問題記述の例である.35を手に入れた場合、計算に問題があることを説明します.サンプル出力が間違っていると疑わないで、自分のアルゴリズムを自分でチェックしてください.
評価用例の規模と約束
30%の評価例について、1≦n≦10、1≦t
i ≤ 20;
60%の評価例について、1≦n≦100、1≦t
i ≤ 100;
100%の評価例について、1≦n≦1000、1≦t
i ≤ 10000.
分析:
石類問題を統合し、動的に計画する.
元のアルゴリズムはdp[n][n]を構築し,n−1からnまでのマージの最小値,n−2からnまでのマージの最小値,,,1からnまでのマージの最小値を後から順に求める.dp[1][n]が答えです.
ここでは、平行四角形の最適化が必要です.最適化後のコードは次のとおりです.
コード:
#include
using namespace std;
#define maxn 0x3f3f3f3f
#define N 1005
int dp[N][N],p[N][N],sum[N];
int main()
{
int n,x;
cin>>n;
sum[0] = 0;
for(int i = 1;i <= n;i++)
{
cin>>x;
sum[i] = sum[i - 1] + x;
dp[i][i] = 0;
p[i][i] = i;
}
for(int l = 1;l < n;l++)
{
for(int i = 1;i <= n - l;i++)
{
int j = i + l,e = 0,temp = maxn;
for(int k = p[i][j - 1];k <= p[i + 1][j];k++)
{
int t = dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1];
if(t < temp)
{
temp = t;
e = k;
}
}
dp[i][j] = temp;
p[i][j] = e;
}
}
cout<