HDU 4963 Dividing a String

http://acm.hdu.edu.cn/showproblem.php?pid=4963

BiBFS
卡了一些怪bug
所以會有一些多餘的codeXD

附上testdata

8
aabbabaabbabaaaa
1 3 7 2
4 2 9 1
5 8 0 6
9 3 8 4

==> 0

8
aabbaabbaabbaabb
203 47 81 99
38 73 97 67
23 11 101 103
91 5 3 1

==>1

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<utility>
using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> pp;
typedef struct _status{ int sts; int pos; int val;}status;
status new_status(int sts, int pos, int val){
    status ret;
    ret.sts = sts;
    if(sts == 1) pos = -1;
    ret.pos = pos;
    ret.val = val;
    return ret;
}
int pushch(int sts, int pos, int ch){
    sts -= 1<<(pos+1);
    sts += ch<<(pos+1);
    sts += 1<<(pos+2);
    return sts;
}
int popch(int sts, int pos, int ch){
    if (sts%2 == ch) return sts>>1;
    return -1;
}
void psts(int a, int n){
    for(int lx = n;lx >= 0;lx--)
        printf("%d", (a&(1<<lx))>>lx);
    return;
}
int rev(int sts){
    int ans = 1;
    while(sts > 1){
        ans <<= 1;
        ans |= sts&1;
        sts >>= 1;
    }
    return ans;
}
int _abs(int a){return max(a, -a);}
int trisearch(vector<int>& t, int val){
    if(t[t.size()-1] <= val) return _abs(t[t.size()-1] - val);
    if(t[0] >= val) return _abs(t[0] - val);
    int tt, tt1, tt2;
    int tts[15], cnt = 0;
    tt = lower_bound(t.begin(), t.end(), val) - t.begin();
    tts[cnt++] = tt-1, tts[cnt++] = tt, tts[cnt++] = tt+1;
    tts[cnt++] = tt-2, tts[cnt++] = tt+2;
    tt = upper_bound(t.begin(), t.end(), val) - t.begin();
    tts[cnt++] = tt-1, tts[cnt++] = tt, tts[cnt++] = tt+1;
    tts[cnt++] = tt+2, tts[cnt++] = tt-2;
    int mm = -1;
    for(int lx = 0;lx < cnt;lx++){
        //if(val == -115)
        //    printf("index = %d\n", tts[lx]);
        if(tts[lx] < 0 or tts[lx] >= t.size()) continue;
        if(mm == -1 or mm >= _abs(t[tts[lx]] - val))
            mm = _abs(t[tts[lx]] - val);
    }
    return mm;
}
status stk[2][2000000];
int main(){
int n;for(;;){
    scanf("%d", &n);
    if(n == 0) break;
    int an[100];
    char str[100];
    int sn[100];
    scanf("%s", str);
    for(int lx = 0;lx < 2*n;lx++){
        scanf("%d", an+lx);
        sn[lx] = str[lx]=='b';
    }
    int left = n + (n%2 == 0);
    int right = 2*n - left;
    int cnt[2]; int lprc = 0;
    stk[lprc][0] = new_status(1, -1, 0);
    cnt[0] = 1; cnt[1] = 0;
    for(int lx = 0;lx < left;lx++){
        int val = an[lx], ch  = sn[lx];
        //printf("to add %d\n", val);
        for(int lx = 0;lx < cnt[lprc];lx++){
            status& gg = stk[lprc][lx];
            //printf("get sts "); psts(gg.sts, gg.pos+1); printf(" = %d\n", gg.val);
            if(gg.pos == -1)
                stk[1-lprc][cnt[1-lprc]++] = new_status(2+ch, 0, gg.val + val);
            else{
                int& pos = gg.pos;
                //printf("%d\n", gg.val + val);
                stk[1-lprc][cnt[1-lprc]++] = new_status(pushch(gg.sts, pos, ch), pos+1, gg.val+val);
                int gp = popch(gg.sts, pos, ch);
                if(gp != -1){
                    if(pos > 0)
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                    else{
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, val-gg.val);
                    }
                }
            }
        }
        cnt[lprc] = 0;
        lprc = 1-lprc;
        //printf("--\n");
    }
    // assert cnt[lprc] < 4e5
    map<int, vector<int> >mleft;
    for(int lx =0;lx < cnt[lprc];lx++){
        mleft[stk[lprc][lx].sts].push_back(stk[lprc][lx].val);
    }
    for(map<int, vector<int> >::iterator it = mleft.begin(); it != mleft.end() ;it++){
        sort(it->second.begin(), it->second.end());
        /*psts(it->first, 10);
        printf("->");
        for(int lx=  0;lx < it->second.size();lx++)
            printf("%d, ", it->second[lx]);
        printf("\n");*/
    }
    lprc = 0; stk[lprc][0] = new_status(1, -1, 0);
    cnt[0] = 1; cnt[1] = 0;
    for(int lx = 0;lx < right;lx++){
        int val = an[2*n - lx-1], ch  = sn[2*n - lx-1];
        for(int lx = 0;lx < cnt[lprc];lx++){
            status& gg = stk[lprc][lx];
            //printf("get sts "); psts(gg.sts, gg.pos+1); printf(" = %d\n", gg.val);
            if(gg.pos == -1)
                stk[1-lprc][cnt[1-lprc]++] = new_status(2+ch, 0, gg.val + val);
            else{
                int& pos = gg.pos;
                //printf("%d\n", gg.val + val);
                stk[1-lprc][cnt[1-lprc]++] = new_status(pushch(gg.sts, pos, ch), pos+1, gg.val+val);
                int gp = popch(gg.sts, pos, ch);
                if(gp != -1){
                    if(pos > 0)
                        stk[1-lprc][cnt[1-lprc]++] = new_status(gp, pos-1, gg.val-val);
                    else{
                        stk[1-lprc][cnt[1-lprc]++] = new_status(1, -1, gg.val-val);
                        stk[1-lprc][cnt[1-lprc]++] = new_status(1, -1, val-gg.val);
                    }
                }
            }
        }
        cnt[lprc] = 0;
        lprc = 1-lprc;
    }
    const int INF_ans = 800000000;
    int ans = INF_ans;
    for(int lx = 0;lx < cnt[lprc];lx++){
        int sts = rev(stk[lprc][lx].sts);
        int val = stk[lprc][lx].val;
        //printf("right sts = "); psts(sts, 10); printf(" val = %d \n", val);

        if(mleft.count(sts) == 0) continue;
        ans = min(trisearch(mleft[sts], val), ans);
        //printf("%d\n", ans);
        //if(ans == -1) printf("%d\n", 1/0);
    }
    if(ans == INF_ans)
        puts("-1");
    else
        printf("%d\n", ans);
}return 0;}