参考博客：https://blog.csdn.net/V5ZSQ/article/details/80205265

题意：

有一串括号，每个括号有一个权值，当遇到前一个括号为’(‘，后一个括号为’)’时，可以进行交换，交换的价值为$v_k*v_{k+1}$，求价值的最大值。

思路：

DP题…没做出来是我的锅QAQ一种转移状态考虑不出来就试着想想别的状态？

每个左括号能到达的最右的位置是固定的，如果这个括号可以被移动到j位置，那么他后面的左括号一定都在比他右的位置，也就是j+1位之后。

第i个左括号到j及之后的位置的最大价值有两种转移，一种是第i个左括号移到j+1及之后的位置，另一种是第i个左括号移到j及之后的位置，第i+1个左括号移到j+1及之后的位置。

有转移方程$dp[i][j]=max(dp[i+1][j],移动到这里的价值+dp[i+1][j+1])$。

如何处理移动到这里的价值呢？

这个价值相当于第i个左括号的权值*pos[i]~j中所有右括号的权值之和。

直接遍历右括号会变成n^3的dp，所以这里用前缀和处理。

处理出前i个右括号的总价值。

为了找出pos[i]~j中所有右括号的编号，要处理出第i个左括号前有多少个右括号。

代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MAXN 10000000
using namespace std;
typedef long long ll;
char s[1010];
ll v[1010];
ll dp[1010][1010];//第i个左括号到j及之后位置的最大分数
int pos[1010];//第i个左括号的下标
ll sum[1010];//前i个右括号的总价值
int pre[1010];//第i个左括号前有多少个右括号
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        scanf("%s",s+1);
        for(int i=1;i<=n;i++)
            scanf("%lld",&v[i]);
        int numl=0,numr=0;
        sum[0]=0;pre[0]=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='(')
            {
                pos[++numl]=i;
                pre[numl]=numr;
            }
            else
            {
                numr++;
                sum[numr]=sum[numr-1]+v[i];
            }
        }
        memset(dp,0,sizeof(dp));
        for(int i=numl;i>=1;i--)
        {
            for(int j=n-numl+i;j>=pos[i];j--)//pos[i]~n-(numl-i)(它后面的左括号都在它后面)
            {
                dp[i][j]=-INF;
                //第pre[i]+1个右括号经过j-pos[i]个右括号到达pre[i]+j-pos[i]
                ll temp=sum[pre[i]+j-pos[i]]-sum[pre[i]];
                dp[i][j]=max(dp[i][j],temp*v[pos[i]]+dp[i+1][j+1]);
                if(j!=n-numl+i)dp[i][j]=max(dp[i][j],dp[i][j+1]);
            }
            for(int j=pos[i]-1;j>=1;j--)
                dp[i][j]=dp[i][j+1];
        }
        ll ans=-INF;
        for(int i=1;i<=n;i++)
            ans=max(ans,dp[1][i]);
        printf("%lld\n",ans);
    }
    return 0;
}