[ZOJ-4027] Sequence Swapping(2018 절강성 경기-D 문제)

BaoBao has just found a strange sequence {, ... } of length n in his pocket. As you can see, each element in the sequence is an ordered pair, where the first element  in the pair is the left parenthesis '(' or the right parenthesis ')', and the second element  in the pair is an integer.
As BaoBao is bored, he decides to play with the sequence. At the beginning, BaoBao's score is set to 0. Each time BaoBao can select an integer k swap the k-th element and the (k+1)-th element in the sequence, and increase his score by (vk*v(k+1)), if and only if 1<=k
BaoBao is allowed to perform the swapping any number of times (including zero times). What's the maximum possible score BaoBao can get?

Input

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains an integer n(1<=n<=10^3), indicating the length of the sequence.
The second line contains a string s(|s|=n) consisting of '(' and ')'. The i-th character in the string indicates si, of which the meaning is described above.
The third line contains n integers v1,v2,......,vn (-10^3<=vi<=10^3). Their meanings are described above.
It's guaranteed that the sum of n of all test cases will not exceed 10^4

Output

For each test case output one line containing one integer, indicating the maximum possible score BaoBao can get.

Sample Input

4
6
)())()
1 3 5 -1 3 2
6
)())()
1 3 5 -100 3 2
3
())
1 -1 -1
3
())
-1 -1 -1

Sample Output

24
21
0
2

Hint

For the first sample test case, the optimal strategy is to select k=2,3,5,4 in order.
For the second sample test case, the optimal strategy is to select k=2,5 in order.
제목:
또한 sk='('그리고 s(k+1)=')'만 교환할 수 있고 양자 가치 곱셈의 가치를 얻을 수 있으며 최대 얼마의 가치를 얻을 수 있는지 물어본다.
아이디어:
저는 dp 방법을 사용합니다. 우선, 이 문제는 왼쪽 괄호와 오른쪽 괄호만 바꿔야 합니다. 이것은 모든 왼쪽 괄호가 도달할 수 있는 가장 오른쪽 위치를 결정합니다. 만약에 이 괄호가 j번째 위치로 이동할 수 있다면 그의 뒤에 있는 왼쪽 괄호는 반드시 그의 오른쪽 위치, 즉 j+1위 뒤에 있을 것입니다.dp[i][j]를 설정하면 i번째 왼쪽 괄호를 j 오른쪽(j 포함) 위치로 이동하면 얻을 수 있는 최대 가치 이동 방정식은 dp[i][j]=max(dp[i+1][j+1]+여기로 이동하면 얻을 수 있는 값, dp[i][j+1])(직접 시작할 수 있다. dp[i+1][j+1]가 처음에는 0이어서 그림자가 없다) 때문에 여기로 이동하면 얻을 수 있는 값은 (이동한 이 왼쪽 괄호의 값)*(그가 교환한 오른쪽 괄호와 괄호),접두사와 몇 개의 오른쪽 괄호를 표시하는 합으로 입력할 때 그 앞에 몇 개의 오른쪽 괄호가 있는지 기록하고 그가 있는 위치에서 그의 오른쪽의 왼쪽 괄호를 빼면 바로 그의 오른쪽의 오른쪽 괄호의 값 수량이다.이를 통해 알 수 있듯이 오른쪽 괄호의 값의 합은 접두사와 (괄호 총수-오른쪽 괄호) - 접두사와 (왼쪽 오른쪽 괄호)이다.
코드:

#include
#define LL long long
#define lowbit(x) x&-x
using namespace std;
const LL MAXN = 100010;
const LL INF = 0x3f3f3f3f;
const double eps = 1e-9;

LL he[1005];
LL dp[1005][1005];
LL kuo[1005];
char chuan[1005];
LL val[1005];
LL wei[1005];
LL zhi[1005];
LL qi[1005];

int main()
{
    LL a,k;
    while(~scanf("%lld",&a))
    {
        while(a--)
        {
            scanf("%lld",&k);
            scanf("%s",chuan);
            LL ru=1;
            kuo[0]=0;
            LL ru1=1;
            for(LL i=0; i=1; i--)
            {
                LL zuo=ru1-i;
                for(LL j=k-1-zuo; j>=wei[i]; j--)
                {
                    LL hou=k-1-j-zuo;
                    LL de=kuo[ru-hou]-kuo[qi[i]];
                    if(j==k-1-zuo)dp[i][j]=zhi[i]*de+dp[i+1][j+1];
                    else dp[i][j]=max(zhi[i]*de+dp[i+1][j+1],dp[i][j+1]);
                    if(i==1)
                    {
                        if(dp[i][j]>jie)jie=dp[i][j];
                    }
                }
                for(LL j=wei[i]-1; j>=wei[i-1]; j--)
                {
                    dp[i][j]=dp[i][j+1];
                    if(i==1)
                    {
                        if(dp[i][j]>jie)jie=dp[i][j];
                    }
                }
            }
            printf("%lld
",jie);
        }
    }
    return 0;
}
/*
5
4
)))(
1 1 1 1
6
)())()
1 3 5 -1 3 2
6
)())()
1 3 5 -100 3 2
3
())
1 -1 -1
3
)))
-1 -1 -1
*/