【ハフマンの木】【欲張り】【NOI 2015】【bzoj 4198】ハマ史詩
6085 ワード
4198:[Noi 2015]ハマ史詩
Description
Allisonは最近文学に夢中になった.彼女はだるい午後、カプチーノを細かく味わい、手放せない「ハマ史詩」を静かに読むのが好きだ.しかし、「オデッセイ」と「イリアット」からなる鴻編巨制「ハマ史詩」は長すぎて、Allisonはコード方式で短くしたいと思っています.
一部の「ハマ史詩」にはn種類の異なる単語があり、1からnまで番号が付けられている.このうちi番目の単語が出現する総回数はwiである.Allisonは、i番目の単語をk進列siで置き換え、以下の要件を満たすようにしたい.
今Allisonは、siをどのように選択すれば、置き換え後に得られる新しい「ハマ史詩」の長さを最小限に抑えることができるかを知りたいと思っています.全長が最小であることを確保した場合、Allisonは最も長いsiの最短長さがどのくらいなのか知りたいと思っています.
1つの文字列はk進文字列と呼ばれ、各文字が0〜k−1の間(0〜k−1を含む)の整数である場合にのみ使用される.
文字列Str 1は、文字列Str 2のプレフィックスと呼ばれ、1≦t≦mが存在する場合にのみ、Str 1=Str 2となる[1..t].ここで、mは文字列Str 2の長さであり、Str 2[1..t]は、Str 2の前のt文字からなる文字列を表す.
Input
入力ファイルの1行目には2つの正の整数n,kが含まれており、中間は単一のスペースで区切られており、n種類の単語が共有されていることを示しており、k進文字列で置き換える必要がある.
次にn行目、i+1行目は1つの非負の整数wiを含み、i番目の単語の出現回数を表す.
Output
出力ファイルは2行です.
1行目は1つの整数を出力し、「ハマ史詩」が再符号化された後の最短長さである.2行目は1つの整数を出力し、最短総長を保証する場合、最長文字列siの最短長を保証する.
Sample Input
Sample Output
HINT
X(k)でXを表すのはk進法で表される文字列です.
1つの最良の態様は、第1の単語を00(2)に置き換え、第2の単語を01(2)に置き換え、第3の単語を10(2)に置き換え、第4の単語を11(2)に置き換えることである.この方式では、符号化後の最短長は、
1×2+1×2+2×2+2×2=12最長文字列siの長さは2である.
1つの非最適案:000(2)を第1の単語に置き換え、001(2)を第2の単語に置き換え、01(2)を第3の単語に置き換え、1(2)を第4の単語に置き換える.この方式では、符号化後の最短長は、
1×3+1×3+2×2+2×1=12最長文字列siの長さは3である.最良のシナリオに比べて、文章の長さは同じですが、最長文字列の長さはもっと長いです.
すべてのデータに対して、2≦n≦100000、2≦k≦9を保証する.選手は64ビット整数で入出力、記憶、計算を行うことに注意してください.
問題:
ハフマンとは思わなかったらひざまずいた.の問題を分析して、出現回数が実は重みであることを発見して、私達が要求するのは1種の符号化方案が重みを×符号化長と最小は,kフォークHuffmanツリーを直接セットして乱すことができる.類比は果実を合併し,逆さまに符号化することを考慮した.リーフノードから符号化を開始し,最小k個数を取り出すたびに1つのxを合成し,符号長に1(実際には逆であるが,実際には同じである)を加算し,xを投げ返す.注意:空のノードがある可能性があります.すなわち、1つのノードの息子がk個未満である可能性があります.これはエラーを防ぐためにゼロを補う必要があります.よく使われる判断方法は、(n-1)%(k-1)で、0はkフォークツリーがいっぱいであることを意味します.(1本の満k叉木に対して、任意のノードにk人の息子がいるか、息子がいないか、葉ノードにx個があるとすると、(n-x)*k=n-1となるので、導いてください)
Code:
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 127 Solved: 80
Description
， 。 ——
Allisonは最近文学に夢中になった.彼女はだるい午後、カプチーノを細かく味わい、手放せない「ハマ史詩」を静かに読むのが好きだ.しかし、「オデッセイ」と「イリアット」からなる鴻編巨制「ハマ史詩」は長すぎて、Allisonはコード方式で短くしたいと思っています.
一部の「ハマ史詩」にはn種類の異なる単語があり、1からnまで番号が付けられている.このうちi番目の単語が出現する総回数はwiである.Allisonは、i番目の単語をk進列siで置き換え、以下の要件を満たすようにしたい.
1≤i,j≤n，i≠j， ：si sj 。
今Allisonは、siをどのように選択すれば、置き換え後に得られる新しい「ハマ史詩」の長さを最小限に抑えることができるかを知りたいと思っています.全長が最小であることを確保した場合、Allisonは最も長いsiの最短長さがどのくらいなのか知りたいと思っています.
1つの文字列はk進文字列と呼ばれ、各文字が0〜k−1の間(0〜k−1を含む)の整数である場合にのみ使用される.
文字列Str 1は、文字列Str 2のプレフィックスと呼ばれ、1≦t≦mが存在する場合にのみ、Str 1=Str 2となる[1..t].ここで、mは文字列Str 2の長さであり、Str 2[1..t]は、Str 2の前のt文字からなる文字列を表す.
Input
入力ファイルの1行目には2つの正の整数n,kが含まれており、中間は単一のスペースで区切られており、n種類の単語が共有されていることを示しており、k進文字列で置き換える必要がある.
次にn行目、i+1行目は1つの非負の整数wiを含み、i番目の単語の出現回数を表す.
Output
出力ファイルは2行です.
1行目は1つの整数を出力し、「ハマ史詩」が再符号化された後の最短長さである.2行目は1つの整数を出力し、最短総長を保証する場合、最長文字列siの最短長を保証する.
Sample Input
4 2
1
1
2
2
Sample Output
12
2
HINT
X(k)でXを表すのはk進法で表される文字列です.
1つの最良の態様は、第1の単語を00(2)に置き換え、第2の単語を01(2)に置き換え、第3の単語を10(2)に置き換え、第4の単語を11(2)に置き換えることである.この方式では、符号化後の最短長は、
1×2+1×2+2×2+2×2=12最長文字列siの長さは2である.
1つの非最適案:000(2)を第1の単語に置き換え、001(2)を第2の単語に置き換え、01(2)を第3の単語に置き換え、1(2)を第4の単語に置き換える.この方式では、符号化後の最短長は、
1×3+1×3+2×2+2×1=12最長文字列siの長さは3である.最良のシナリオに比べて、文章の長さは同じですが、最長文字列の長さはもっと長いです.
すべてのデータに対して、2≦n≦100000、2≦k≦9を保証する.選手は64ビット整数で入出力、記憶、計算を行うことに注意してください.
問題:
ハフマンとは思わなかったらひざまずいた.の問題を分析して、出現回数が実は重みであることを発見して、私達が要求するのは1種の符号化方案が重みを×符号化長と最小は,kフォークHuffmanツリーを直接セットして乱すことができる.類比は果実を合併し,逆さまに符号化することを考慮した.リーフノードから符号化を開始し,最小k個数を取り出すたびに1つのxを合成し,符号長に1(実際には逆であるが,実際には同じである)を加算し,xを投げ返す.注意:空のノードがある可能性があります.すなわち、1つのノードの息子がk個未満である可能性があります.これはエラーを防ぐためにゼロを補う必要があります.よく使われる判断方法は、(n-1)%(k-1)で、0はkフォークツリーがいっぱいであることを意味します.(1本の満k叉木に対して、任意のノードにk人の息子がいるか、息子がいないか、葉ノードにx個があるとすると、(n-x)*k=n-1となるので、導いてください)
Code:
#includereturn a.l h;
int n,k,nn; LL ans=0;
int in(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
LL Lin(){
LL x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+(LL)(ch-'0'),ch=getchar();
return x;
}
int main(){
n=in(),k=in(); nn=n;
for (int i=1; i<=n; i++){
LL x=Lin();
h.push((H){x,1});
}
if ((n-1)%(k-1)) nn+=(k-1)-((n-1)%(k-1));
for (int i=n+1; i<=nn; i++)
h.push((H){0,1});
while (nn>1){
LL s1=0; int s2=0;
for (int i=1; i<=k; i++){
H x=h.top(); h.pop();
s1+=x.w; s2=max(s2,x.l);
}
ans+=s1; nn-=(k-1);
h.push((H){s1,s2+1});
}
printf("%lld
%d
",ans,h.top().l-1);
return 0;
}