dp问题的状态设计都是十分巧妙，根据y总的说法，可以把他看作集合，对于转移，考虑最后一个不同量/
对于dp状态，首先要观察题目的信息，看他有什么，我认为所有的dp的状态都能从题目中猜出来，这题目告诉你括号可以移动。
我们进一步发现，左括号只能与右括号相换，所以所有左括号的相对顺序是不变的，同理右括号也是所以我们可以想到根据这个性质设计状态。
再观察本题的数据范围，1000，说明可能要开二维数组。这样符合题目的数据，当然每道题都不一定一样，但是出题人不可能乱出数据
所以这道题由此可以推断大概率是二维dp，复杂度是N^2，这就能满足条件。对于线性dp的第一维，一般都是前i个某值，或者第i个某值。所以主要是对第二维状态的分析
题目的信息不多，我们要求取的答案是价值的最大，并且这题不是可行性问题，所以我们自然考虑按照常理把价值作为dp数组需要表示的量而不是第二维
那么剩下只有括号移动这一个性质。并且dp题目要考虑到无后效性，所以本题的难点就是想到同一类括号的相对顺序是不变的。所以设计状态为
第i个左括号移动到j这个位置及以后能得到最大的价值是多少，（前i个是倒着数的，因为右边左括号的位置决定了左边左括号的移动范围）。为什么要设计成j以后呢，因为这样方便转移
所以方程就是 f[i][j]=max(f[i+1][j+1]+v,f[i][j+1])，所以dp方程的定义都要做到不会漏掉状态，我们这个方程的意思是，可以从第i个移到j+1以后，和第i+1个移到j+1以后+i个移到这个位置的最大值转移过来。
这样就包含了所有状态。最后的答案自然是f[cnt[1]][1]表示的是最后一个左括号移到第一个位置及后面。这肯定是答案，cnt表示的是倒序的左括号的数量
#include<iostream> #include<cstring> #include<cstdio> #include<map> #include<algorithm> #include<queue> #define ull unsigned long long using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; ll f[1010][1010]; ll sum[N],b[N]; ll a[N]; int p[N]; int cnt[N]; int main(){ int i; int t; cin>>t; while(t--){ int n; string s; cin>>n; cin>>s; s=" "+s; for(i=1;i<=n;i++){ cin>>a[i]; } cnt[n+1]=0; sum[0]=0; int tot=0; memset(f,0,sizeof f); for(i=n;i>=1;i--){ cnt[i]=cnt[i+1]+(s[i]=='('?1:0); if(s[i]==')'){ sum[tot+1]=sum[tot]+a[i]; tot++; } else{ p[i]=tot; } } ll ans=0; for(i=n;i>=1;i--){ if(s[i]==')') continue; int j; for(j=n-cnt[i]+1;j>=i;j--){ f[cnt[i]][j]=f[cnt[i]-1][j+1]+a[i]*(sum[p[i]]-sum[n-j+1-cnt[i]]); } for(j=n-cnt[i];j>=1;j--){ f[cnt[i]][j]=max(f[cnt[i]][j],f[cnt[i]][j+1]); } } ans=f[cnt[1]][1]; cout<<ans<<endl; } }