锐客网

  1. 首页 > 生活百科 > it技术 > >

zoj4027 Sequence Swapping

IT知识Sequencepingswap

一卷旌收千骑虏，万全身出百重围。这篇文章主要讲述zoj4027 Sequence Swapping相关的知识，希望能为你提供帮助。
首先容易想到二维方程dp(i,j)，表示第i个左括号去匹配到第j个右括号时产生的最大值，但如果如此表示的话，首先需要枚举(i，j)以及一个k即dp(i-1,k)。
【zoj4027 Sequence Swapping】考虑变化dp(i,j)的表示方法，可选择将其表示为第i个左括号至少匹配到第j个右括号时所产生的最大值。如此表示的话，则转移方程为
dp(i,j) = max(dp(i,j+1),dp(i+1,j) + a(i,j))此时不再需要枚举k了，其中a(i,j)表示由第i个左括号匹配到第j个右括号时得到的值。另外注意左括号不去匹配右括号时的情况，
这个情况需要另行添加。

#include< cstdio> #include< cstdlib> #include< iostream> #include< string> #include< set> #include< algorithm> #include< vector> #include< queue> #include< list> #include< cmath> #include< cstring> #include< map> #include< stack> using namespace std; #define INF 0x3f3f3f3f #define maxn 200005 #define ull unsigned long long #define ll long long #define hashmod 99999839 #define mod 7 #define repe(x,y,i) for(int i=(x); i< =(y); ++i) #define repne(x,y,i) for(int i=(x); i< (y); ++i) #define MAX(x,y) (x) < (y) ? (y) : (x); char s[1005]; int p0[1005],p1[1005]; ll v[1005]; ll a[1005][1005]; ll dp[1005][1005]; //第i个0至少匹配到第j个1产生的最大值 int main(){ // freopen("a.in","r",stdin); //freopen("b.out","w",stdout); int T,n; cin > > T; while(T--){ scanf("%d",& n); scanf("%s",s); int st = 0,en = n - 1,len0,len1; for(int i = 0; i < n; ++i) scanf("%lld",& v[i]); for(; s[st] != ‘(‘; ++st); for(; s[en] != ‘)‘; --en); len0 = len1 = 1; //存在不进行匹配的情况放到0 for(int i = st; i < = en; ++i){ if(s[i] == ‘(‘) p0[len0++] = i; else p1[len1++] = i; } memset(a,0,sizeof(a)); for(int i = 1; i < len0; ++i){//预处理前缀和 int l = p0[i]; for(int j = 1; j < len1; ++j){ if(l < p1[j]) a[i][j] = a[i][j-1] + v[l] * v[p1[j]]; } } memset(dp,0,sizeof(dp)); dp[len0-1][len1 - 1] = a[len0-1][len1-1]; ll ans = 0; for(int i = len1 - 2; i > = 0; --i) dp[len0 - 1][i] = max(a[len0-1][i],dp[len0-1][i+1]); for(int i = len0 - 2; i > = 0; --i){ dp[i][len1 - 1] = dp[i+1][len1 - 1] + a[i][len1 - 1]; for(int j = len1 - 2; j > = 0; --j){ dp[i][j] = max(dp[i][j+1],dp[i+1][j]+a[i][j]); if(i == 0) ans = max(dp[i][j],ans); } } printf("%lld ",ans); } return 0; }

 

    推荐阅读


    上一篇：Java并发编程原理与实战四十一（重排序 和 happens-before）

    下一篇：android在主线程下载文件