HDU-4963 Dividing a String(列挙[途中出会い法])

Dividing a String
http://acm.hdu.edu.cn/showproblem.php?pid=4963 Time Limit: 30000/15000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Problem Description
Let S be a string of length 2*N, where each character in S is assigned an integer as its weight. The weight of a subsequence T of S, denoted by weight(T), is defined as the sum of all its characters’ weights. Your task is to divide S into two subsequences T1 and T2, each of length N, such that:
1.T1 is equal to T2.
2.|weight(T1) – weight(T2)| is as small as possible.
 
Input
The input contains multiple test cases. 
Each case consists of three lines. 
The first line contains an integer N (1<=N<=20). 
The second line is a string S of length 2*N. Each character in S is either ‘a’ or ‘b’. The third line contains 2*N positive integers, where the ith integer is the weight of the ith character in S. No integer exceeds 1000000.
The input is terminated by N = 0.
 
Output
For each case, output the smallest difference between weight(T1) and weight(T2) in a line. If it is impossible to divide S into two equal subsequence, output -1 instead.
 
Sample Input

   
   
   
   

    
    
    
    2
abab
3 1 10 5
3
aaabbb
1 1 1 2 2 2
3
abaaba
4 6 5 10 3 4
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    11
-1
2
   
   
   
   

問題解をざっと見た.
大まかな考え方は、前半と後半をそれぞれ列挙し、前半を列挙する場合、T 1の長さがT 2の長さより小さく、かつ題意を満たす場合、T 1は必ずT 2の接頭辞であり、T 2がT 1より多く出た列をCとし、複雑度をO(2^n)とする.同様に,後半を列挙する場合,T 1がT 2より多く出た列をCCとする.C=CCのみの場合、T 1=T 2となるので、全てのCに対応するsumからCCに対応するsumの絶対値を減算した最小値が解答となる
最初はソートされていませんが、dfs_がわかります.backは1枚につき1つのCCを挙げて保存したCの中で片側を遍歴し,TLEを招き,さらに問題解をよく見ると,並べ替えた後に隣接する2つのCとCCを列挙すれば,1つ隔てた場合に隣接するものより小さくないことが証明される.
修正後もWAを続け、最後にユニットデータをランダムにしたところ、短い文字列に文字を追加した場合、接頭辞にnum[i]==((c>(j-k-1)&1)を使うべきかどうかを判断し、num[i]=((c&(1<(j-k-1))を書き始めた.あ、この間違いは逆順dfs_backのCC文字列の時に出たことがありますが、タイムリーに修正しました、ここでは注意していません…あとは左右に移動した結果に注意して、当然とは思えません
便宜上ab列をバイナリで表し,また01や001などは区別できないため,列の一番前に1を加えるとすべての長さの異なる列を区別できる.
速度は速くて、2.5 sぐらいで、時間は一時的に2番目に並んでいます:)しかし、空間の占有量はわりに大きいです

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

struct Node {
    int sum,type;
    Node(int _sum,int _type):sum(_sum),type(_type) {}
    bool operator< (const Node& a) const {
        return sum<a.sum;
    }
};

int ans,w[45],n,num[45],mn,mx;
int que[4200005],times=0;
vector<Node> weight[2100005];

void dfs_front(int i,int j,int k,int sumT1,int sumT2,int c) {//        
    if(i>=n) {//       
        if(j<=k) {//|T1|<=|T2|
            if(weight[c].size()==0)
                que[times++]=c;
            weight[c].push_back(Node(sumT2-sumT1,0));
            mx=max(mx,c);
            mn=min(mn,c);
        }
        return ;
    }
    if(j<k) {
        if(num[i]==((c>>(k-j-1)&1)))//  T1    num[i]   T2   
            dfs_front(i+1,j+1,k,sumT1+w[i],sumT2,(c&(~(1<<(k-j))))|(1<<(k-j-1)));//     T1
        dfs_front(i+1,j,k+1,sumT1,sumT2+w[i],(c<<1)|num[i]);//     T2
    }
    else if(j>k){
        dfs_front(i+1,j+1,k,sumT1+w[i],sumT2,(c<<1)|num[i]);
        if(num[i]==((c>>(j-k-1))&1))//  T2    num[i]   T1   
            dfs_front(i+1,j,k+1,sumT1,sumT2+w[i],(c&(~(1<<(j-k))))|(1<<(j-k-1)));
    }
    else {
        dfs_front(i+1,j+1,k,sumT1+w[i],sumT2,(c<<1)|num[i]);
        dfs_front(i+1,j,k+1,sumT1,sumT2+w[i],(c<<1)|num[i]);
    }
}

void dfs_back(int i,int j,int k,int sumT1,int sumT2,int c) {//        
    if(i<n) {
        if(j>=k) {// |T1|>=|T2|
            int l=j-k-1,r=0;
            while(l>r) {//         ，               ，    
                if(((c>>l)&1)!=((c>>r)&1)) {//            （    ）
                    c^=1<<l;
                    c^=1<<r;
                }
                --l;
                ++r;
            }
            if(weight[c].size()==0)
                que[times++]=c;
            weight[c].push_back(Node(sumT1-sumT2,1));
            mx=max(mx,c);
            mn=min(mn,c);
        }
        return ;
    }
    if(j<k) {
        if(num[i]==((c>>(k-j-1)&1)))//  T1    num[i]   T2   
            dfs_back(i-1,j+1,k,sumT1+w[i],sumT2,(c&(~(1<<(k-j))))|(1<<(k-j-1)));//     T1
        dfs_back(i-1,j,k+1,sumT1,sumT2+w[i],(c<<1)|num[i]);//     T2
    }
    else if(j>k){
        dfs_back(i-1,j+1,k,sumT1+w[i],sumT2,(c<<1)|num[i]);
        if(num[i]==((c>>(j-k-1))&1))//  T2    num[i]   T1   
            dfs_back(i-1,j,k+1,sumT1,sumT2+w[i],(c&(~(1<<(j-k))))|(1<<(j-k-1)));
    }
    else {
        dfs_back(i-1,j+1,k,sumT1+w[i],sumT2,(c<<1)|num[i]);
        dfs_back(i-1,j,k+1,sumT1,sumT2+w[i],(c<<1)|num[i]);
    }
}


int main() {
    //freopen("in.txt","r",stdin);
    int cnt[3];
    char s[45];
    while(scanf("%d",&n),n!=0) {
        while(times>0)
            weight[que[--times]].clear();
        cnt[0]=cnt[1]=0;
        scanf("%s",s);
        for(int i=0;i<(n<<1);++i) {
            scanf("%d",w+i);
            num[i]=s[i]-'a';// ab      01 
            ++cnt[num[i]];//  0 1     
        }
        if(((cnt[0]&1)==1)||((cnt[1]&1)==1)) {
            printf("-1
");
            continue;
        }
        mx=0;
        mn=21000005;
        ans=0x3f3f3f3f;
        dfs_front(0,0,0,0,0,1);
        dfs_back((n<<1)-1,0,0,0,0,1);

        for(int c=mn;c<=mx;++c) {
            if(weight[c].size()>1) {
                sort(weight[c].begin(),weight[c].end());
                int j=-1,k=-1;
                for(int i=0;i<weight[c].size();++i) {
                    if(weight[c][i].type==0)
                        j=i;
                    else
                        k=i;
                    if(j!=-1&&k!=-1)
                        ans=min(ans,abs(weight[c][j].sum-weight[c][k].sum));
                }
            }
        }
        printf("%d
",ans==0x3f3f3f3f?-1:ans);
    }
    return 0;
}