狀態(tài)壓縮是信息學(xué)競賽中一個很常見的方法，最最常見的是二進制壓位。
做過USACO的同學(xué)會知道有很多搜索和DP都可以用狀態(tài)壓縮優(yōu)化。
一般來講，如果狀態(tài)的夠成非常多，但每個構(gòu)成相對簡單，就可以狀態(tài)壓縮，比如巨大的0/1矩陣等。
當(dāng)然如果狀態(tài)壓縮，提取每個數(shù)據(jù)起來就會耗費更多的時間，所以一般運用在狀態(tài)復(fù)制量較大，比較量較小的情況下。
舉例：
多關(guān)鍵字排序可以用狀態(tài)壓縮，如A，B，C三個關(guān)鍵字，均小于100，可以壓縮成A*10000+B*100+C，直接比較即可，非常方便。
N皇后的狀態(tài)壓縮，配合位運算，神速。
相鄰兩行之間的匹配關(guān)系，壓成二進制，做DP。
其實只要想節(jié)約空間都可以用狀態(tài)壓縮。
壓縮通式：0<a<A 0<b<B 0<c<C (關(guān)鍵程度a>=b>=c) <==> T=a*B*C+b*C+c ,A*B*C<maxstruct
為了方便一般使A=B=C，轉(zhuǎn)換成A進制數(shù)即可
（*）狀態(tài)壓縮的效率：
常見的把5個小于100的數(shù)壓成一個longint的數(shù)，如果是5個小于50的數(shù)呢？
1.空間利用率:顯然按十進制壓縮的空間效率太低，可以考慮按50為一個單元壓縮，
2.時間效率：提取時大量的取模和除法運算使效率太低，可以考慮換成64進制的數(shù)，進行壓縮。
這里的空間又有了一定程度上的浪費，也體現(xiàn)了時間與空間的辯證關(guān)系。