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