sdut 1451 括號東東 DP

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

題意:中文.....

思路:

pku有一道題,經典的括號匹配(區間DP)題目,那道題目是求的最長滿足條件的子串的長度,那里的子串與這里的子串條件不一樣。

詳細:http://www.cnblogs.com/E-star/archive/2013/01/28/2879385.html

對于這個例子

)((())))(()())

pku的最長子串是12

而這里是6?

這里我們是求的連續的滿足的子串。

dp[i]表示0到i的最長的滿足的連續的子串

則有:

if(str[i - dp[i - 1] - 1] == '(' && str[i] == ')') dp[i] = dp[i - dp[i - 1] - 1] + 2;

if (dp[i - dp[i - 1] - 2])

dp[i] += dp[i - dp[i - 1] - 2]

//#pragma comment(linker,"/STACK:327680000,327680000")
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>#define CL(arr, val)    memset(arr, val, sizeof(arr))#define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0)
#define ll long long
#define L(x)    (x) << 1
#define R(x)    (x) << 1 | 1
#define MID(l, r)   (l + r) >> 1
#define Min(x, y)   (x) < (y) ? (x) : (y)
#define Max(x, y)   (x) < (y) ? (y) : (x)
#define E(x)        (1 << (x))
#define iabs(x)     (x) < 0 ? -(x) : (x)
#define OUT(x)  printf("%I64d\n", x)
#define lowbit(x)   (x)&(-x)
#define Read()  freopen("din.txt", "r", stdin)
#define Write() freopen("dout.txt", "w", stdout);#define N 1000007
using namespace std;int dp[N];
int ans,num;
char str[N];
int n;int main()
{//  Read();int i;while (~scanf("%s",str)){n = strlen(str);CL(dp,0);num = 0; ans = 0;for (i = 1; i < n; ++i){if (i - dp[i - 1] - 1 >= 0 && str[i - dp[i - 1] - 1] == '(' && str[i] == ')'){dp[i] = dp[i - 1] + 2;if (i - dp[i - 1] - 2 >= 0 && dp[i - dp[i - 1] -2] != 0){dp[i] += dp[i - dp[i - 1] - 2];}}if (ans < dp[i]){ans = dp[i];num = 1;}else if (ans == dp[i]) num++;}if (ans == 0) printf("0 1\n");elseprintf("%d %d\n",ans,num);}return 0;}

  

?

轉載于:https://www.cnblogs.com/E-star/archive/2013/01/28/2880420.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/376873.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/376873.shtml
英文地址,請注明出處:http://en.pswp.cn/news/376873.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

CDN緩存替代算法

CDN緩存工作過程如下&#xff1a;用戶發出一個請求&#xff0c;如果請求被命中&#xff0c;緩存將對用戶的請求進行響應&#xff0c;返回其請求的數據&#xff1b;如果未被命中&#xff0c;緩存向上拉取用戶需要的數據&#xff0c;并對其存儲的數據進行替換。 緩存算法的意義在…

前端開發常用正則表達式

1、電話 var phone /(^[^1][0-9\-]{6,20}$)|(^(134|135|136|137|138|139|150|151|152|157|158|159|182|183|187|188|147|130|131|132|155|156|185|186|145|133|153|180|189|181|184)\d{8}$)/ 2、郵箱 var email /^([a-zA-Z0-9_.-])([a-zA-Z0-9_-])((\.[a-zA-Z0-9_-]{2,3}){1,…

android 中調用接口發送短信

轉載&#xff1a;http://ziyu-1.iteye.com/blog/1013932 android中可以通過兩種方式發送短信 第一&#xff1a;調用系統短信接口直接發送短信&#xff1b;主要代碼如下&#xff1a; Java代碼//直接調用短信接口發短信 SmsManager smsManager SmsManager.getDefault(); List…

linux 命令案例學習——文件搜索

兩個搜索文件的工具 locate ——僅僅通過文件名查找文件find ——依據文件的各種屬性在既定目錄&#xff08;包括子目錄&#xff09;里查找一個通常與文件搜索命令一起使用、處理搜索結果文件列表的命令 xargs1 locate 1.1 查找文件名中含有zip的文件名 locate zip 看下結…

Redis 緩存擊穿、緩存穿透、緩存雪崩的處理方法

常用的分布式緩存Redis單機并發量能達到萬級&#xff0c;常用的關系型數據庫MySQL一般并發量是千級&#xff0c;他們支持的并發量可能差十倍&#xff0c;所以要盡可能把流量攔截在緩存層。 緩存擊穿 一個并發訪問量比較大的key在某個時間過期&#xff0c;導致所有的請求直接打…

Java-- 異常與記錄日志

可以使用java.util.logging工具將輸出記錄在日志中。記錄日志的的功能還是很簡單的&#xff0c;下面直接鋪出代碼&#xff1a; 1 package com.exceptions;2 3 import java.io.*;4 import java.util.logging.Logger;5 6 class LoggingException extends Exception{7 private…

圖像處理基礎

圖像處理基礎 在計算機中&#xff0c;按照顏色和灰度的多少可以將圖像分為二值圖像、灰度圖像、索引圖像和真彩色RGB圖像四種基本類型。目前&#xff0c;大多數圖像處理軟件都支持這四種類型的圖像。 (1) 二值圖像&#xff1a;一幅二值圖像的二維矩陣僅由0、1兩個值構成&#x…

緩存一致性解決方法

對于緩存 數據庫讀寫&#xff0c;有個經典的Cache Aside Pattern&#xff1a; 讀取&#xff1a;先讀取緩存&#xff0c;緩存里沒有&#xff0c;讀取數據庫&#xff0c;然后返回響應&#xff0c;順便保存緩存&#xff1a; 更新&#xff1a;先更新數據庫&#xff0c;然后刪除緩…

使用SpringMVC的表單驗證

上一篇搭建了基本項目&#xff0c;這一篇在此基礎上加入表單驗證功能。 第一步&#xff0c;添加command類 Java代碼 package test.bean; import javax.validation.constraints.Size; public class User { Size(min3,max30) private String username; …

hdu1247(Hat’s Words)

我以為像a、aa這樣的輸入應該是沒有輸出的&#xff0c;結果還是要輸出aa。 建樹的時候就是常規建樹&#xff0c;不過查找的時候要做一些變形&#xff1a;對于一個單詞&#xff0c;從第一位檢查有沒有單詞是它的前綴&#xff0c;如果有的話&#xff0c;再去檢查它的后半部分是不…

單體、分布式、微服務、Serverless軟件架構一覽

目錄軟件架構單體架構分布式應用微服務架構Serverless架構總結Reference軟件架構 軟件架構就是軟件的基本結構&#xff0c;合適的架構是軟件成功的最重要因素之一。這里列舉了目前流行的4種軟件架構。 單體架構 典型的三級架構&#xff1a;前端&#xff08;web/手機端&#…

MyBatis3 association error - The content of element type resultMap must match (constructor?,id*,r...

MyBatis3 association error - The content of element type "resultMap" must match "(constructor?,id*,result*,association*,collection*,discriminator?)" 1.后臺錯誤信息-問題現象&#xff1a; ERROR [geby:Context initialization failed] 2013-0…

Midjourney V6刷屏,但它最可怕的地方居然不是那些神圖?

Midjourney在沉寂九個月后推出了Midjourney V6&#xff0c;這個文生圖產品體現出的更細膩的細節處理&#xff0c;更強大的語言理解能力和更加“不像AI”的圖片效果在過去幾天引發一片驚呼。 作為一個閉源的模型產品&#xff0c;Midjourney的魔法配方并不為人所知&#xff0c;但…

HTTP 錯誤500.19 -Internal Server Error

HTTP 錯誤500.19 -Internal Server Error 原文:HTTP 錯誤500.19 -Internal Server Error HTTP 錯誤500.19 -Internal Server Error 錯誤代碼 0x80070021 asp.net 2009-11-05 16:54:33 閱讀484 評論1 字號&#xff1a;大中小 錯誤摘要 HTTP 錯誤500.19 -Internal Server Error …

連續內存分區式內存管理

目錄前言分區式內存管理動態分區內存管理總結本筆記參考黃工的https://mp.weixin.qq.com/s/k0W_LqI1zBAYC1GU1U2HQA 前言 內存管理模塊主要負責內存的初始化、分配以及釋放。 從分配內存是否連續可以分為兩大類&#xff1a; 1、連續內存管理 為進程分配的內存空間是連續的&a…

用DEVC++作圖

小海豚學NOIP&#xff0c;老師說要用DEV C。 小海豚喜歡畫圖&#xff0c;記得以前用C#編些程序給她看。可前一陣打開看&#xff0c;我的免費Visual Studio過期了。可惡的Microsoft &#xff0c;不想用盜版難道就要每個月就下載一次&#xff1f; 于是就用DEV C的Windows調用吧。…

Python服務器開發三:Socket

Python服務器開發三&#xff1a;Socket socket是操作系統中I/O的延續&#xff0c;它可以使進程和機器之間的通信成為可能。socket可以看成一個標準的文件描述符。不同的是文件需要用open()函數打開&#xff0c;而socket用socket() 函數建立.recv()、send()函數和read()、write(…

Syntax error: Bad for loop variable解決辦法

在Ubuntu下寫的shell文件t.sh執行時出現錯誤&#xff1a; 1 t.sh: 6: Syntax error: Bad for loop variable 從ubuntu 6.10開始&#xff0c;ubuntu就將之前默認的bash shell更換成了dash shell&#xff0c;其表現為/bin/sh鏈接倒了/bin/dash&#xff0c;而不是傳統的/bin/bash&…

Linux命令常見

摘自&#xff1a; 常考的 21 條 Linux 命令 目錄&#xff09;cd,切換路徑ls,查看文件與目錄的命令cp,用于復制文件mv,用于移動文件、目錄cat,查看文件內容find&#xff0c;文件搜索文件權限命令&#xff0c; 設置權限&#xff0c;-取消權限文本處理命令打包和壓縮文件命令進程相…

記一次調試

這是我最近幾個月來遇到的最棘手的一個問題&#xff1a;* 昨天花了4個小時找出第一層次的原因這個糾結啊&#xff0c;本來和老婆說好準時下班回家吃飯的&#xff0c;結果被這個問題拖了老久。這是一個gradle的plugin&#xff0c;用來resolve公司內部的dependency的&#xff0c;…