POJ 2955 Brackets

来源:http://www.cnblogs.com/Silenceneo-xw/archive/2016/10/07/5936944.html
-Advertisement-
Play Games

Brackets Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6622 Accepted: 3558 Description We give the following inductive definition of a “r ...


Brackets

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 6622   Accepted: 3558

Description

We give the following inductive definition of a “regular brackets” sequence:

  • the empty sequence is a regular brackets sequence,
  • if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
  • if a and b are regular brackets sequences, then ab is a regular brackets sequence.
  • no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < imn, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

Source

Stanford Local 2004     題目大意:給你一個長度不超過100的括弧序列,求最長合法括弧子序列的長度。合法的括弧序列滿足下列條件: 1.空的括弧序列是合法的; 2.如果一個括弧序列s是合法的,那麼(s)和[s]都是合法的; 3.如果兩個括弧序列a和b都是合法的,那麼ab也是合法的; 4.其他的括弧序列都是不合法的。 例如:(), [], (()), ()[], ()[()]都是合法的,而(, ], )(, ([)], ([(]都是不合法的。   解題思路:一道典型的區間DP模型題目。分析一下問題,可以發現:如果找到一對匹配的括弧,例如[xxx]oooo,就把區間分成兩部分,一部分是xxx,另一部分是oooo。 設dp[i][j]表示區間[i,j]之間的最長合法括弧子序列的長度,那麼當i<j時,如果區間[i+1,j]內沒有與i匹配的括弧,則dp[i][j]=dp[i+1][j];如果存在一個與之匹配的k,那麼dp[i][j]=max{dp[i+1][j], dp[i+1][k-1]+dp[k+1][j]+1(i<=k<=j&&i和k是一對匹配的括弧)}。因此,我們將整個串長作為區間進行搜索,那麼最後2*dp[0][len-1]即為答案,len表示串的長度。詳見代碼。     附上AC代碼:
 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 const int maxn = 105;
 5 char str[maxn];
 6 int dp[maxn][maxn];
 7 
 8 bool match(char a, char b){
 9     return (a=='('&&b==')') || (a=='['&&b==']');
10 }
11 
12 int dfs(int l, int r){
13     if (l >= r)
14         return 0;
15     if (l+1 == r)
16         return dp[l][r] = match(str[l], str[r]);
17     if (dp[l][r])
18         return dp[l][r];
19     int ans = dfs(l+1, r);
20     for (int i=l; i<=r; ++i)
21         if (match(str[l], str[i])){
22             int t = dfs(l+1, i-1)+dfs(i+1, r)+1;
23             if (t > ans)
24                 ans = t;
25         }
26     return dp[l][r] = ans;
27 }
28 
29 int main(){
30     while (~scanf("%s", str) && str[0]!='e'){
31         memset(dp, 0, sizeof(dp));
32         int len = strlen(str);
33         dfs(0, len-1);
34         printf("%d\n", 2*dp[0][len-1]);
35     }
36     return 0;
37 }
View Code

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 什麼是Optional對象 Java 8中所謂的Optional對象,即一個容器對象,該對象可以包含一個null或非null值。如果該值不為null,則調用isPresent()方法將返回true,且調用get()方法會返回該值。 另外,該對象還有其它方法: 如可以使用orElse()方法給Opti ...
  • 裝飾器實際上就是函數,可以在裝飾器中置入通用功能的代碼來降低程式的複雜度。 功能: >引入日誌 >增加計時邏輯來檢測性能 >給函數加入事務的能力 例子1、簡單裝飾器 例子2、含返回值的裝飾器 例子3、複雜裝飾器 這裡是含參數的裝飾器,在裝飾器中調用before方法和after方法,完成對List方法 ...
  • RabbitMQ簡介 AMQP,即Advanced Message Queuing Protocol,高級消息隊列協議,是應用層協議的一個開放標準,為面向消息的中間件設計。消息中間件主要用於組件之間的解耦,消息的發送者無需知道消息使用者的存在,反之亦然。AMQP的主要特征是面向消息、隊列、路由(包括 ...
  • f you are not familiar with MySQL stored procedures or want to review it as a refresher, you can follow the MySQL stored procedures tutorial. We will ...
  • 為什麼要引入繼承?   還是做一個媒體庫,裡面可以放CD,可以放DVD。如果把CD和DVD做成兩個沒有聯繫的類的話,那麼在管理這個媒體庫的時候,要單獨做一個添加CD的函數,單獨做一個添加DVD的函數,如果還要往這個媒體庫里添加其他的媒體類,還要再創建另一個添加函數。我們說這樣的代碼不具備可擴展性。... ...
  • 收集整理一些常用的PHP類庫,資源以及技巧. 有中英兩種版本,以便在工作中迅速的查找所需。 ...
  • 在我前面的文章(http://www.cnblogs.com/homewch/p/5749850.html)中有提到R可以自定義啟動環境,需要修改R安裝文件中的ect文件夾下的配置文件Rprofile.site即可: Rprofile.site文件里,設置的內容包括預設編輯器,CRAN鏡像選取,自動 ...
  • Python 學習之路 目錄介紹 一、Python 介紹 python的創始人是吉多·範羅蘇姆.Python於1989年的聖誕節期間誕生. 二、Python 的主要應用領域 雲計算:OpenStack是python語言開發的 web開發:典型web框架有Django 科學運算\人工智慧:典型庫Num ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...