51nod-1791-합법적인 괄호 세그먼트

7208 단어 얼떨결에 드디어 ACdp
괄호 서열이 하나 있는데, 지금 그것이 얼마나 많은 비공식 자단이 합법적인 괄호 서열인지 계산해 보아야 한다.
올바른 괄호 시퀀스의 정의는 다음과 같습니다.
1. 빈 서열은 합법적인 괄호 서열이다.
2. S가 합법적인 괄호 서열이라면 (S)는 합법적인 괄호 서열이다.3. A와 B가 모두 합법적인 괄호 서열이라면 AB는 합법적인 괄호 서열이다.
Input 다중 그룹 테스트 데이터첫 번째 줄에는 테스트 데이터의 수량을 나타내는 정수 T(1<=T<=1100000)가 있다.다음 T행은 각 행에 괄호 서열이 있고'('와')로 구성된 비공렬입니다.모든 입력한 괄호 서열의 총 길이는 1100000을 초과하지 않습니다.Output은 테스트 데이터에 대한 답변을 각 행에 맞게 T 행을 출력합니다.Sample Input 5 ( () ()() (() (()) Sample Output 0 1 3 1 2
제1반응: 이 타당한 dp.그리고 한참 동안 컨디션 전환을 생각했는데 다 틀렸어.상태 dp[i]를 i번째 괄호로 끝나는 합법적인 괄호 자단의 수량으로 정의하면 dp[i]=dp[pos[i]-1]+1(pos[i]는 i번째 괄호와 일치하는 왼쪽 괄호의 위치) 그리고 답은 모든 dp값을 합치는 것이다.이유: (스스로 규칙을 찾아봐...QAQ) 그리고 창고 저장과 오른쪽 괄호가 일치하는 왼쪽 괄호를 발견?memset을 쓰지 마세요. 이 문제의 결과는 롱롱을 써야 할 것 같아요.상세한 것은 코드를 보십시오.
#include
#include
#include
#define maxn 1100005
using namespace std;
int t,n,dp[maxn];
char s[maxn];
stack<int> sk;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",s+1);
		n=strlen(s+1);
		while(!sk.empty()) sk.pop();
		long long ans=0;
		for(int i=1;i<=n;i++)
		{
			dp[i]=0;
			if(s[i]==')')
			{
				if(!sk.empty())
				{
					int l=sk.top();sk.pop();
					dp[i]=dp[l-1]+1;
					ans+=1ll*dp[i];
				}
			}
			else sk.push(i);
		}
		printf("%lld
",ans);
	}
}
2. 파이톤이 접미사된 다변수 해석 4-2.인자 분석 [인자수의 추정]
코드로 모니터링

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage