TIOJ 1482 孔明棋 [狀態壓縮]

poao899    1482    Accepted    27640K    227MS    G++    0.79K    2010-04-05 19:42:47                 .


對吼忘了只要記走訪過所以不需要DP= =





















//****************************************

#include<stdio.h>
int stat[1<<23][24], n, ss;
char in[20];
inline bool getbit(int q, int st){
    return st& (1<<q);
}
void dp(int st, int n){
    if(stat[st][n])return;
    int cnt=0, t1, t2, t3;
    for(int i=0; i<n; ++i){
        cnt+= getbit(i, st);
    }
    stat[st][n]= cnt;
    for(int i=0; i+2<n; ++i){
        if(getbit(i+1, st)){
            t1= getbit(i, st);
            t2= getbit(i+2, st);
            if(t1^t2){
                t3= st^(1<<(i))^(1<<(i+1))^(1<<(i+2));
                dp(t3, n);
                if(stat[t3][n]< stat[st][n])
                    stat[st][n]= stat[t3][n];
            }
        }
    }
}
int main(){
    while(~scanf("%d\n", &n)){
        gets(in);
        ss= 0;
        for(int i=0; in[i]; ++i)
            ss=(ss<<1)+(in[i]=='o');
        dp(ss, n);
        printf("%d\n", stat[ss][n]);
    }
}