sdut 1451 括号东东 (dp或模拟)-白红宇

sdut 1451 括号东东 (dp或模拟)

阅读量：7307 次

发布时间：2019-06-30

本文共 1470 字，大约阅读时间需要 4 分钟。

题目：http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1451

这个题弄了好久，其实这个中文就挺难理解的，，一开始理解错题意了，，

然后后来问了问ZJH学长题意，弄明白的，提交之后还是不对，后来回到宿舍之后问了问LMM学姐，感觉他的方法很好还有就是用dp了

一、用栈模拟

思路：利用一个标记数组，a[]，用于记为第i个字符是否为合法字符，若是则标记为1，否则标记为0，

最后便利一遍，最长合法字串就是最长的连续的1的长度，子串的个数就是有几段连续的i就是几

二、dp

dp[]数组存储i位置最长的合法子串的长度，

代码：

View Code

1 #include 
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 char str[1000010]; 6 int dp[1000010]; 7 int main() 8 { 9 10     while(scanf("%s",str)!=EOF)11     {12         int len=strlen(str);13         int i;14         dp[0]=0;15         int sum=0,num=1;16         for(i=1;i
         
          =0&&str[i]==')'&&str[i-dp[i-1]-1]=='(')//有与i位置的‘）’匹配的‘（’19             {20                 dp[i]=dp[i-1]+2;21                 if(i-dp[i-1]-2>=0&&dp[i-dp[i-1]-2]!=0)//如果与i位置匹配的位置的前一位置还有匹配的括号时，要加上那个位置的值22                 {23                     dp[i]+=dp[i-dp[i-1]-2];24                 }25                 if(dp[i]>sum)26                 {27                     sum=dp[i];28                     num=1;29                 }30 31                 else if(sum==dp[i]&&sum!=0)32                 {33                     num++;34                 }35             }36             else37             {38                 dp[i]=0;39             }40         }41         cout<
          
           <<" "<
           
            <