Problem G: 三队-杭州-划分字符串
Problem G: 三队-杭州-划分字符串Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 36 Solved: 8
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.
The input contains multiple test
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.
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.
3 1 10 5
1 1 1 2 2 2
4 6 5 10 3 4