CCF圧縮符号化
1566 ワード
1つの整数nを与えて、次のn個の整数、それぞれ各文字の出現頻度(順序によって与える)を表して、あなたに1種の符号化方式を与えることを要求して、各文字の符号化が辞書の順序によって並べた後の順序がもとの順序と同じで、この前提の下で全体の符号化の長さが最小であることを望みます.この最小長さを出力します.
問題解:符号化長が最小であることを見ると、一般的にはハフマン符号化が考えられ、まして問題もハフマン符号化を挙げたが、実際にはこれは穴だ.問題は,各文字の符号化が辞書順に並べられた順序が元の順序と同じであることを前提としている.したがって,重み値が最も小さい2つのノードを毎回取り出すことはできず,隣接するノードしか選択できず,どの隣接するノードを選択するかが石の問題である.
dp[i][j]はi番目からj番目の堆石の合併の最適値を表し、sum[i][j]はi番目からj番目の堆石の総数を表す.状態遷移式があります.
1、dp[i][j]=0 (i==j)
2、dp[i][j]=min(dp[i][k]+dp[k][j])+sum[i][j] (i!=j)
このときアルゴリズムはO(n^3)と複雑であり,ここでは平行四角形最適化を用いてO(n^2)に下げることができる.
上記の方程式から,dp[i][j]を求めるたびに適切なk値を見つけることが重要であり,p[i][j]をdp[i][j]とするこの適切なk値は,平行四角形規則に基づいて以下の不等式がある:p[i][j-1]<=p[i][j]<=p[i+1][j]である.
では、dp[i][i+L](Lは長さ)を解く複雑さは、
(p[2,L+1]-p[1,L])+(p[3,L+2]-p[2,L+1])…+(p[n-L+1,n]-p[n-L,n-1])=p[n-L+1,n]-p[1,L]≤n.
複雑度はO(n)である.そしてLが1からnにループすると,総複雑度はO(n^2)となる.
コードは次のとおりです.
問題解:符号化長が最小であることを見ると、一般的にはハフマン符号化が考えられ、まして問題もハフマン符号化を挙げたが、実際にはこれは穴だ.問題は,各文字の符号化が辞書順に並べられた順序が元の順序と同じであることを前提としている.したがって,重み値が最も小さい2つのノードを毎回取り出すことはできず,隣接するノードしか選択できず,どの隣接するノードを選択するかが石の問題である.
dp[i][j]はi番目からj番目の堆石の合併の最適値を表し、sum[i][j]はi番目からj番目の堆石の総数を表す.状態遷移式があります.
1、dp[i][j]=0 (i==j)
2、dp[i][j]=min(dp[i][k]+dp[k][j])+sum[i][j] (i!=j)
このときアルゴリズムはO(n^3)と複雑であり,ここでは平行四角形最適化を用いてO(n^2)に下げることができる.
上記の方程式から,dp[i][j]を求めるたびに適切なk値を見つけることが重要であり,p[i][j]をdp[i][j]とするこの適切なk値は,平行四角形規則に基づいて以下の不等式がある:p[i][j-1]<=p[i][j]<=p[i+1][j]である.
では、dp[i][i+L](Lは長さ)を解く複雑さは、
(p[2,L+1]-p[1,L])+(p[3,L+2]-p[2,L+1])…+(p[n-L+1,n]-p[n-L,n-1])=p[n-L+1,n]-p[1,L]≤n.
複雑度はO(n)である.そしてLが1からnにループすると,総複雑度はO(n^2)となる.
コードは次のとおりです.
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
const int inf=0x08080808;
int mmin(int a,int b){
return aval) {
dp[i][j]=val;
p[i][j]=k;
}
}
//cout<