CCF 201612-4圧縮符号化(100点)
試験問題番号:
201612-4
試験問題名:
あっしゅくコーディング
時間制限:
3.0s
メモリの制限:
256.0MB
問題の説明:
問題は、既知の単語a 1,a 2,...,anが現れる頻度がそれぞれt 1,t 2,...,tnである文字を記述する.各単語が1つの01列に対応するように、これらの単語を01列で符号化することができ、いずれの単語の符号化(対応する01列)も別の単語で符号化されたプレフィックスではなく、この符号化をプレフィックス符号と呼ぶ.プレフィックスコードを使用して文字を符号化することは、その文字の各単語を順番に符号化することを意味する.1段の文字が接頭辞で符号化された長さは、L=a 1の符号化長である×t 1+a 2の符号化長×t 2+...+anの符号化長×tn. 接頭辞符号化を辞書シーケンス符号化として定義すると、1≦i nに対して、aiの符号化(対応する01列)の辞書シーケンスがai+1符号化の前、すなわちa 1,a 2,...,anの符号化が辞書シーケンス昇順に配列されることを指す.例えば、文字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行目は、a 1,a 2,...,anの出現頻度、すなわちt 1,t 2,...,tnをそれぞれスペースで区切ったn個の整数を含む.a 1,a 2,...,anが具体的にどんな単語なのかは本題の解に影響しないので,a 1,a 2,...,anは入力されていないことに注意してください.出力フォーマットは、文字が符号化された長さLの最小値を示す整数を出力する.サンプル入力5 1 3 4 2 5サンプル出力34サンプルは、このサンプルが問題記述の例であることを示す.35を手に入れた場合、計算に問題があることを説明します.サンプル出力が間違っていると疑わないで、自分のアルゴリズムを自分でチェックしてください.評価用例の規模と約束は30%の評価用例に対して、1≦n≦10、1≦ti≦20である.60%の評価例について、1≦n≦100、1≦ti≦100;100%の評価例では、1≦n≦1000、1≦ti≦10000であった.
問題リンク:CCF 20612-4圧縮符号化
問題解析もんだいかいせき:石の問題,四角形の不等式を使用した最適化,いしのもんだい,しへんけいのふとうしきをしよう
プログラム説明:dp[i][j]は、i番目の堆石をj番目の堆石に合併する最小費用を表す
提出後100点を得たC++プログラム:
201612-4
試験問題名:
あっしゅくコーディング
時間制限:
3.0s
メモリの制限:
256.0MB
問題の説明:
問題は、既知の単語a 1,a 2,...,anが現れる頻度がそれぞれt 1,t 2,...,tnである文字を記述する.各単語が1つの01列に対応するように、これらの単語を01列で符号化することができ、いずれの単語の符号化(対応する01列)も別の単語で符号化されたプレフィックスではなく、この符号化をプレフィックス符号と呼ぶ.プレフィックスコードを使用して文字を符号化することは、その文字の各単語を順番に符号化することを意味する.1段の文字が接頭辞で符号化された長さは、L=a 1の符号化長である×t 1+a 2の符号化長×t 2+...+anの符号化長×tn. 接頭辞符号化を辞書シーケンス符号化として定義すると、1≦i nに対して、aiの符号化(対応する01列)の辞書シーケンスがai+1符号化の前、すなわちa 1,a 2,...,anの符号化が辞書シーケンス昇順に配列されることを指す.例えば、文字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行目は、a 1,a 2,...,anの出現頻度、すなわちt 1,t 2,...,tnをそれぞれスペースで区切ったn個の整数を含む.a 1,a 2,...,anが具体的にどんな単語なのかは本題の解に影響しないので,a 1,a 2,...,anは入力されていないことに注意してください.出力フォーマットは、文字が符号化された長さLの最小値を示す整数を出力する.サンプル入力5 1 3 4 2 5サンプル出力34サンプルは、このサンプルが問題記述の例であることを示す.35を手に入れた場合、計算に問題があることを説明します.サンプル出力が間違っていると疑わないで、自分のアルゴリズムを自分でチェックしてください.評価用例の規模と約束は30%の評価用例に対して、1≦n≦10、1≦ti≦20である.60%の評価例について、1≦n≦100、1≦ti≦100;100%の評価例では、1≦n≦1000、1≦ti≦10000であった.
問題リンク:CCF 20612-4圧縮符号化
問題解析もんだいかいせき:石の問題,四角形の不等式を使用した最適化,いしのもんだい,しへんけいのふとうしきをしよう
プログラム説明:dp[i][j]は、i番目の堆石をj番目の堆石に合併する最小費用を表す
提出後100点を得たC++プログラム:
#include
#include
using namespace std;
const int INF=0x7f7f7f7f;
const int N=1005;
int sum[N];//
int dp[N][N];
int p[N][N];
int main()
{
int n;
memset(dp,INF,sizeof(dp));
memset(sum,0,sizeof(sum));
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
dp[i][i]=0;
p[i][i]=i;
}
//DP
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
for(int k=p[i][j-1];k<=p[i+1][j];k++){
int val=dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1];
if(dp[i][j]>val){
dp[i][j]=val;
p[i][j]=k;
}
}
}
}
printf("%d
",dp[1][n]);
return 0;
}