精华内容
下载资源
问答
  • 给定括号形式的 N 个输入闭区间: Ii := [left(i),right(i)], i = 1,2...,N(数学符号)。 集合union(Ii)可以按间隔Jk写为规范分区; 即,union{Ii) = union(Jk),其中Jk 是M 个区间(M<=N,所以分区是最小...
  • 区间dp-括号匹配

    2019-07-21 19:23:34
    区间dp 搞得我有点懵,理解了好久才稍微有一点点感觉,区间dp 就是对区间进行动态规划; 一般线性dp有四个步骤: 1.把原问题转换为子问题; 2.找状态(就是确定dp为几维); 3.寻找边界; 4.确定转移方程;(也...

    区间dp 搞得我有点懵,理解了好久才稍微有一点点感觉,区间dp 就是对区间进行动态规划;

    一般线性dp有四个步骤:

    1.把原问题转换为子问题;

    2.找状态(就是确定dp为几维);

    3.寻找边界;

    4.确定转移方程;(也是最关键的一步);

    而区间dp第二步就已经确定,一般情况为二维,dp[i][j]就表示从 i 到 j 的最优解;

    区间dp经典的题目:

    括号匹配:

    Description

    括号匹配是一个常见的问题,我们定义,规则的括号序列满足以下几点
    1.空序列是规则括号序列。
    2.如果s是规则括号序列,则(S)和[s]是规则括号序列。
    3.如果a和b是规则括号序列,则ab是规则括号序列。
    例如:(), [], (()), ()[], ()[()],这些都是匹配的。
    例如:(, ], )(, ([)], ([(],这些都是不匹配的。
    现在我们想知道一个只由(,),[,]这四种字符组成的字符串,该字符串子序列中最长的规则括号序列有多长。

    Input

    第1行1个正整数 t,表示t组数据(n<=10)。
    之后每行一个字符串,字符串只由(,),[,]组成。字符串长度<=100

    Output

    每行输出最长规则的括号序列长度。

    Sample Input Copy

    5
    ((()))
    ()()()
    ([]])
    )[)(
    ([][][)

    Sample Output Copy

    6
    6
    4
    0
    6
    

    代码:

    #include<bits/stdc++.h>
    using namespace std;
    int dp[110][110];
    int main()
    {
        int t;
        while(~scanf("%d",&t))
        {
            char a[110];
            while(t--)
            {
                memset(dp,0,sizeof(dp));
                scanf("%s",a+1);
                int len=strlen(a+1);
                for(int i=2; i<=len; i++)
                    for(int j=1; j<=len; j++)
                    {
                        int k=i+j-1;
                        if(k<=len)
                        {
                            if(a[j]=='('&&a[k]==')'||a[j]=='['&&a[k]==']')
                                dp[j][k]=dp[j+1][k-1]+2;
                            for(int m=j; m<k; m++)
                                dp[j][k]=max(dp[j][k],dp[j][m]+dp[m][k]);
    
                        }
                    }
                printf("%d\n",dp[1][len]);
            }
        }
        return 0;
    }
    

     

    展开全文
  • 区间dp入门(括号匹配)

    千次阅读 2018-08-28 23:59:05
    题目一:括号合法匹配: 题意:给定一个由()[]四种符号组成的字符串,求其中合法满足合法匹配的最长子串的长度。合法匹配有如下几种形式:()、[]、(合法串)、[合法子串]、合法子串+合法子串+....(如()[][][]()[]...

    题目一:括号合法匹配:

    题意:给定一个由()[]四种符号组成的字符串,求其中合法满足合法匹配的最长子串的长度。合法匹配有如下几种形式:()、[]、(合法串)、[合法子串]、合法子串+合法子串+....(如()[][][]()[])。

    分析:

    dp问题三个重要环节:描述状态、状态转移方程、递推边界。

    区间dp的话状态描述一般为二位数组,表示起点和终点。

    因为是入门,我们暂且假设已经分析出该题为区间dp,所以状态描述就有了,dp[i][j]表示从i到j最长合法子串的长度。。。

    首先我们先来看一下有一个字符的情况,比如结果为0,;两个字符的时候呢,如果这两个字符相同,为0+2,否则,还是0;再看3个字符的时候,即在2个字符的基础上加一个字符,此时的最大值可能为1+2的形式或者2+1的形式(分段);分为四段时,则有可能为1+3、2+2,3+1三种形式,显然我们需要枚举断点,且取多种形式中的最大值作为结果:

    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);其实这样看的话还少了两种形式:0+4和4+0,(可视作一种);

    而对于这一形式所需要的dp值dp[i][j]我们是不知道的,所以我们可以先处理这种情况,其值由dp[i+1][j-1]得来,如果区间两端元素相同,上式dp值+2,否则,就等于dp[i+1][j-1](其实上述分段取值时已经包含了两端字符不相等时的情况,所以else可以省去),这样的话状态转移方程也就有了:

    1:if(str[i]==str[j])dp[i][j]=dp[i+1][j-1]+2;

    2:dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);

    第三递推边界的话较容易考虑,但不太好想的地方是断点的范围,因为断点的选择决定了我们应该対哪些初始状态赋值,所以这个地方应该手动模拟一下,防止重复计算或者遗漏状态。

    AC代码:

    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include<algorithm>
    #include <set>
    #include <queue>
    #include <stack>
    #include<vector>
    #include<map>
    #include<ctime>
    #define ll long long
    #define INF 0x7fffffff
    using namespace std;
    ll dp[110][110];
    int main()
    {
        string str;
        while(cin>>str&&str!="end")
        {
            memset(dp,0,sizeof(dp));
            ll n=str.length();
            for(ll len=1;len<n;++len)//枚举长度
            {
                for(ll j=0;j<=n-2&&j+len<=n-1;++j)
                {
                    if(str[j]=='('&&str[j+len]==')'||str[j]=='['&&str[j+len]==']')
                    {
                        dp[j][j+len]=dp[j+1][j+len-1]+2;
                    }
                    for(ll k=j;k<j+len;++k)
                    {
                        dp[j][j+len]=max(dp[j][j+len],dp[j][k]+dp[k+1][j+len]);
                    }
                }
            }
            cout<<dp[0][n-1]<<endl;
            str.clear();
    
        }
        return 0;
    
    }
    

     

    展开全文
  • ACM题集:... Princess Principal ... 题意:使用数组代表括号,0,1为一对左右括号,1,2为另一对,3,4。。。同理。给定n个括号,查询m次[l,r]范围是否匹配合法。 解...

    ACM题集:https://blog.csdn.net/weixin_39778570/article/details/83187443
    Princess Principal
    题目:https://ac.nowcoder.com/acm/contest/201/J
    题意:使用数组代表括号,0,1为一对左右括号,1,2为另一对,3,4。。。同理。给定n个括号,查询m次[l,r]范围是否匹配合法。
    解法:查询次数比较多,使用一个数组记录括号匹配情况,topp[i]表示从i开始往左边第一个匹配不上的位置,那么[L,r]区间是否匹配可以转换为topp[L-1]是否等于topp[r],若相等则说明区间[l,r]可以完全匹配,因为topp[r]一定往左越过了L,括号是否匹配的话,依然用一个栈来维护,匹配上了就把左括号出栈,匹配不上就进栈,左括号,直接进栈。栈顶一定为当前位置往左第一个匹配不上的位置
    解法二:仍然用栈来存储,由于匹配方式是唯一的,我们用一个数组 b[i] 来记录第 i个括号所匹配的括号的位置。若一个区间内的括号完全匹配,当我们从区间内取出一个单括号时,它所匹配的括号也必然在这个区间内,这种性质称为“封闭性”。
    然后我们预处理每个括号所匹配括号的位置即b[i],但是查询的时候复杂度仍然是线性的。然而我们只需要对区间(l,r)求所匹配的括号位置的最值进行查询即可,换言之,若区间(l,r)所匹配的括号的最大值或者最小值不在(l,r)里,那么就违反了“封闭性”。问题就转换成了求区间最值,我们可以采用RMQ或线段树解决。

    #include<bits/stdc++.h>
    #define ll long long
    #define fo(i,j,n) for(register int i=j; i<=n; ++i)
    using namespace std;
    const int maxn = 1e6+5;
    int n,m,q;
    ll a[maxn],ttop[maxn];//a表示括号类型 
    void pend(){
    	stack<ll> st; // 存放下标 
    	ttop[0] = 0;  // 初始状态,可以理解为第0个不匹配 
    	fo(i,1,n){ // 0,1  2,3  4,5 为不同括号(第0,1,2种) 
    		if(st.empty() || !(a[i]&1)) st.push(i); // 如果栈空,或者遇到左括号加入栈
    		else{
    			if(a[i] == a[st.top()]+1) st.pop(); // 右括号匹配上了左括号,去掉左括号
    			else st.push(i);  // 匹配不上加(下标) 入栈  
    		}
    		if(st.empty()) ttop[i] = 0; // 栈空表示中间都能匹配,都是合法的 
    		else           ttop[i] = st.top(); // 匹配不上的情况下ttop[i]=i, 匹配上了ttop[i]=往左边第一个匹配不上的下标 
    	}
    }
    int main(){
    	scanf("%d%d%d",&n,&m,&q);
    	fo(i,1,n) scanf("%lld",&a[i]);
    	pend();
    	int l,r;
    	while(q--){
    		scanf("%d%d",&l,&r);
    		if(ttop[l-1]==ttop[r])puts("Yes"); // 表示第l-1个和第r个往左第一个匹配不上的下标相同 
    		else puts("No");				   // 如果相同则说明了r这个括号匹配不上的下标已经跳过了[l,r]这个范围,说明[l,r]完全匹配 
    	} 
    } 
    
    

    解法二:ST算法

    #include<bits/stdc++.h>
    #define ll long long
    #define fo(i,j,n) for(register int i=j; i<=n; ++i)
    using namespace std;
    const int maxn = 1e6+5;
    int n,m,q;
    int a[maxn], b[maxn]; // b数组储存匹配上的括号的下标 
    stack<int> st;
    int dp_max[maxn][20],dp_min[maxn][20];  // 数组大小maxn, log(n)/log(2)
    // dp[i][j] 表示 [i,i+2^j -1] 的最值 
    void ST(){
    	fo(i,1,n){
    		dp_max[i][0] = b[i];
    		dp_min[i][0] = b[i];
    	}
    	int t = log(n)/log(2);
    	fo(j,1,t){
    		for(int i=1; i+(1<<j)-1<=n; i++){
    			dp_max[i][j] = max(dp_max[i][j-1], dp_max[i+(1<<(j-1))][j-1]);
    			dp_min[i][j] = min(dp_min[i][j-1], dp_min[i+(1<<(j-1))][j-1]); 
    		}
    	}
    }
    int RMQ_min(int l, int r){
    	int k = log(r-l+1)/log(2);
    	return min(dp_min[l][k], dp_min[r-(1<<k)+1][k]);
    }
    int RMQ_max(int l, int r){
    	int k = log(r-l+1)/log(2);
    	return max(dp_max[l][k], dp_max[r-(1<<k)+1][k]);
    }
    int main(){
    	scanf("%d%d%d",&n,&m,&q);
    	fo(i,1,n){
    		scanf("%d",&a[i]);
    		b[i] = -1;
    		if(st.empty() || !(a[i]&1))st.push(i);
    		else{
    			if(a[i] == a[st.top()]+1){
    				// 两个位置都要匹配上 
    				b[i] = st.top();
    				b[st.top()] = i;
    				st.pop();
    			}else st.push(i); 
    		}
    	}
    	ST();
    	int L,R;
    	fo(i,1,q){
    		scanf("%d%d",&L,&R);
    		if(RMQ_min(L,R)>=L && RMQ_max(L,R)<=R) puts("Yes");
    		else puts("No");
    	}
    	return 0;
    } 
    
    展开全文
  • 括号匹配 (区间dp)

    2018-05-16 20:35:14
    区间dp ...思路:dp[i][j]表示区间i~j的最大匹配数,对于dp[i][j] = dp[i + 1][j - 1] + (s[i]和s[j]匹配?2 : 0),开始时dp[i][j]均为0。 代码如下: #include &lt;cstdio&gt; #inclu...

    区间dp

    题目大意:给出一个的只有’(‘,’)’,’[‘,’]’四种括号组成的字符串,求最多有多少个括号满足匹配。
    题目链接
    思路:用dp[i][j]表示区间i~j的最大匹配数,对于dp[i][j] = dp[i + 1][j - 1] + (s[i]和s[j]匹配?2 : 0),开始时dp[i][j]均为0。
    代码如下:

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1e2 + 100;
    char str[maxn];
    int dp[maxn][maxn];
    
    int main()
    {
        while(~scanf("%s", str) && strcmp(str, "end"))
        {
            memset(dp, 0, sizeof(dp));
            int n = strlen(str);
            for(int len = 2; len <= n; len++)
            {
                for(int i = 0; i < n; i++)
                {
                    if(i + len - 1 > n) break;
                    int j = i + len - 1;
                    if((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']'))
                    {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                    else dp[i][j] = dp[i + 1][j - 1];
    
                    for(int k = i; k < j; k++)
                    {
                        dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
            printf("%d\n", dp[0][n - 1]);
        }
    }

    括号匹配升级:
    问最少加多少括号,能使其完全匹配。加上个记录路径。
    比如:( [ ( ] 最少加两个 变为 ( ) [ () ]

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1e2 + 100;
    const int INF = 0x3f3f3f3f;
    char str[maxn];
    int dp[maxn][maxn], tag[maxn][maxn];
    
    // tag[i][j]用于记录区间[i, j]在哪里断开
    // dp[i][j]表示区间[i, j]最少的不匹配的数量。
    
    void print(int l, int r) {
       if(l > r) return ;
       if(l == r) {
          if(str[l] == '(' || str[r] == ')') printf("()");
          else printf("[]");
          return ;
       }
       if(tag[l][r] == -1) {
          printf("%c", str[l]);
          print(l + 1, r - 1);
          printf("%c", str[r]);
       }
       else {
          print(l, tag[l][r]);
          print(tag[l][r] + 1, r);
       }
    }
    
    int main()
    {
        while(~scanf("%s", str))
        {
            memset(dp, 0, sizeof(dp));
            memset(tag, -1, sizeof(tag));
            int n = strlen(str);
            if(n == 0) {
            printf("\n");
            continue;
         }
            for(int i = 0; i <= n; i++) dp[i][i] = 1; //一个的时候是1
    
            for(int len = 2; len <= n; len++)
            {
                for(int i = 0; i < n; i++)
                {
                    if(i + len - 1 >= n) break;
                    int j = i + len - 1;
                    dp[i][j] = dp[i + 1][j - 1];
                    if((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']'))
                    { }
                    else dp[i][j] += 2;
                    //当str[i]与str[j]匹配时,dp[i][j] = dp[i + 1][j - 1]
                    //不匹配时,加2
    
                    for(int k = i; k < j; k++)
                    {
                        if(dp[i][j] >= dp[i][k] + dp[k + 1][j]) { //要加=号是因为']('这样的情况,在没进第三个for的时候就已经变成了2,[0,1]区间应该被分割开加符号,但是tag记录不到。
                            dp[i][j] = dp[i][k] + dp[k + 1][j];
                            tag[i][j] = k;
                        }
                    }
                }
            }
    
            print(0, n - 1);
            printf("\n");
        }
    }
    

    附紫书上的做法:

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e3 + 100;
    const int inf = 0x3f3f3f3f;
    
    int dp[maxn][maxn], tag[maxn][maxn];
    char str[maxn];
    
    bool match(char a, char b) {
       if((a == '(' && b == ')') || (a == '[' && b == ']')) return true;
       return false;
    }
    
    void print(int l, int r) {
       if(l > r) return ;
       if(l == r) {
          if(str[l] == '(' || str[r] == ')') printf("()");
          else printf("[]");
          return ;
       }
       if(tag[l][r] == -1) {
          printf("%c", str[l]);
          print(l + 1, r - 1);
          printf("%c", str[r]);
       }
       else {
          print(l, tag[l][r]);
          print(tag[l][r] + 1, r);
       }
    }
    
    int main()
    {
         gets(str);
         int len = strlen(str);
         if(len == 0) {
            printf("\n");
            return 0;
         }
         for(int i = 0; i < len; i++)
         {
             dp[i][i] = 1;
    
         }
    
         memset(tag, -1, sizeof(tag));
    
         for(int i = len - 2; i >= 0; i--)
         {
             for(int j = i + 1; j < len; j++)
             {
                 dp[i][j] = len + 1;
                 if(match(str[i], str[j])) dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
                 for(int k = i; k < j; k++)
                 {
                     if(dp[i][j] > dp[i][k] + dp[k + 1][j])
                     {
                         dp[i][j] = dp[i][k] + dp[k + 1][j];
                         tag[i][j] = k;
                     }
                 }
             }
         }
    
    
         print(0, len - 1);
         printf("\n");
    }
    展开全文
  • 法1:dp[i][j]表示i~j之间的字符串匹配数,这之间存在两种情况,一种是([]),也就是嵌套型,即i和j位置的括号可以匹配,所以dp[i][j]=dp[i+1][j-1]+2,另一种是()[],所以dp[i][j]=dp[i][k]+dp[k+1][j]这些所有的...
  • Sample Input ((())) ()()() ([]]) )[)( ([][][) end Sample Output 6 6 4 0 6 思路: 题意:找出给定字符串中最大能够匹配上的括号数量; dp[i][j]表示[i,j]这段区间里面的最长子序列的长度,当s[i] =s[j] 是,可以...
  • 区间DP-括号匹配问题

    2020-08-26 21:59:17
    这次学习的过程中主要是有前缀和思想,就是一个一位数组来存放从[0,i]这个区间的值的和,若要知道一段区间的值的和,只需要将[0,i]的前缀和减去[0,j]的前缀和即可。 区间dp的一般框架为 for len 1 to maxsize for ...
  • 获取大括号括号内容 项目开发用到了,暂做个简单记录 private static String regex = "\\{([^}]*)\\}";//匹配大括号 private static String regexx = "\\(([^}]*)\\)";//匹配小括号 public static void main...
  • UVA1626 括号序列 Brackets sequence 简单的区间DP,但是要输出方案,所以我们按照转移的方法再重新来一遍即可。 输出时考虑四种情况: i>j不存在这种子串,返回0 i==j子串长度为1说明是一个孤立点,所以要消耗...
  • 两个题的链接:括号匹配1括号匹配2 首先我们看第一题 是很简单的区间dp 问一个符号串 最大的完美匹配数是多少 表示区间l到r最大的完美匹配数 根据区间dp的性质 是由较小的区间向较大的区间转移 根据题意一开始的...
  • 题意:在一个长度为n的区间里,你可以在两端(左端或者右端)取出一个数,这个数乘以他是第几次取出来的。求和的最大值。 思路:一眼贪心模拟简单题。后来发现不行一旦一个数字很大就没法贪心了。给个数据 5 90 80 1...
  • 觉得这个题目,输出是个大问题,所以pos数组来标记某一段区间的情况,如果某一段区间【i , j】上从k处切断有更小补足的解,就pos【i】【j】=k的形式来保存,如果区间【i,j】的两端是对称的,即不用更改括号,则...
  • 置信区间

    千次阅读 2019-07-12 21:34:03
    相关名词解释 区间估计:给定置信水平,根据估计值确定真实值可能出现的区间范围,该区间通常以...置信区间括号[a,b]表示样本估计总体平均值误差范围的区间。a、b的具体数值取决于你对于”该区间包含总体均...
  • 总结收获 题目 传送门 题意: N表示人的个数为2*N,M表示不同的好朋友的对数。(N<=200) 最开始2N个人排列成1,2,…,...很像括号匹配,所以就是区间DP,然后现在考虑怎么转移; 在求区间[i,j]的时候,所有小的区间
  • 括号匹配(区间dp)

    2018-06-07 20:47:27
    给你一个字符串,里面只包含"(",")","[","]"四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。 如: []是匹配的 ([])[]是匹配的 ((]是不匹配的 ([)]是不匹配的 输入 第一行输入一个正整数N,表示测试...
  • 区间DP:括号子序列

    2020-05-13 20:03:39
    Vjudge:经典区间DP问题,括号匹配。c++
  • 括号配对(区间DP)

    2021-03-10 00:04:28
    Hecy 又接了个新任务:BE 处理。 BE 中有一类被称为 GBE。 以下是 GBE 的定义: 空表达式是 GBE 如果表达式 A 是 GBE,则 [A] 与 (A) 都是 GBE 如果 A 与 B 都是 GBE,那么 AB 是 GBE 下面给出一个 BE,求至少添加...
  • 括号序列(区间dp)

    2019-10-02 14:32:37
    括号序列(区间dp) 输入一个长度不超过100的,由"(",")","[",")"组成的序列,请添加尽量少的括号,得到一个规则的括号序列。如有多解,输出任意一个序列即可。 括号序列是这样定义而成的: 空序列是括号序列 ...
  • 思路:经典括号匹配问题,区间dp:小区间推大区间,枚举区间大小,然后枚举起点。 若s[i]与s[j]括号匹配,则dp[i][j] = dp[i+1][j-1]+2,然后枚举i到j区间内的每个点,更新dp[i][j] = max(dp[i][j],dp[i][x]+dp[x+1][j]). ...
  • 区间dp括号匹配

    2017-05-04 17:46:42
    题目#include<bits/stdc++.h>using namespace std;typedef long long LL;int t; int n; int dp[110][110]; string s; bool judge(int i,int j) ... if(s[i-1]=='('&&s[j-1]==')' || s[i-1]=='['&&s[j-1]==']') return
  • 一般来说,选定某一个置信区间,我们的目的是为了让"ab之间包含总体平均值"的结果有一特定的概率,这个概率就是所谓的置信水平。 例如我们最常用的95%置信水平,就是说做100次抽样,有95次的置信区间包含了总体均值...
  • 括号匹配(二) 时间限制:1000 ms | 内存限制:65535 KB 难度:6 描述 给你一个字符串,里面只包含”(“,”)”,”[“,”]”四种符号,请问你需要至少添加多少个括号才能使这些括号匹配起来。 如: []是匹配的...
  • 状态dp[i][j]表示从i区间到j区间内的匹配括号数。 状态转移方程 if(i和j匹配)  dp[i][j]=dp[i+1][j-1]+2 dp[i][j]=max{dp[i][k]+dp[k][j]}k为最优分割点 #include #include #include #include...
  •   /* /*/ #include &lt;bits/stdc++.h&gt; using namespace std; #define inf 0x3f3f3f3f const int N=35; int n,a[N],dp[N][N],sum[N]; char s[N]; inline bool judge(int i,int j){ ...a...
  • 区间dp理解 添加最少的括号使得括号字符串匹配思路分享
  • 区间DP——括号匹配

    2015-03-30 22:11:09
    区间DP——括号匹配
  • 区间dp 模板题 坑点:初值ans若为-1 碰到长度为1的括号串 输出的结果是-1而不是0 #include<iostream> #include<algorithm> #include<string.h> #include<map> #include<queue> #...
  • [......] 方括号表达式
  • HUNNU oj 11757 Brackets————区间dp (括号匹配) 这里我从Brackets的代码基础上加以改造。 这道题的要求是,给一段括号序列,添加最少的括号来使这个序列是匹配的。 我的思路是:先求出给出序列的最长匹配...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,231
精华内容 18,092
关键字:

区间用什么括号