합법적인 괄호식의 최대 길이 구법 (우선순위가 없을 때)
단순 DP는 가장 긴 합법적인 서브열과 합법적인 서브열의 개수를 구한다. dp[i]는 i를 끝으로 가장 긴 합법적인 서브열을 대표한다. (의 dp값은 모두 0이고 (의 길이는 계산은 있는지 없는지를 보아야 한다) 하나를 읽을 때 왼쪽에 인접한 기호가 (, 이)의 dp값에 2를 더하면 이 단락()이 인접한 왼쪽도 합법적인지 판단해야 한다. 예를 들어 ()()의 경우 기호 1, 2, 3, 4를 표시한다. 이때 dp[3]=2, dp=0, [3dp]=0dp[2]=2, dp[1]=0, 앞의 합법적인 직렬, 즉 dp[i-1]을 건너뛰어야 한다. 여기는 0이다. i에서 되돌아가면 현재 짝을 맞춘 ()도 지나야 하기 때문에 앞의 끝('('왼쪽이 합법적인 단락이 있다면)은 dp[i-dp[i-1], 즉 dp[2]이다. 그 위에 dp[4]=dp[4]+dp[4-0-2]=4를 더한다.하나를 읽을 때 왼쪽이 서로 인접하지 않으면 (((((((() 합법적인 직렬, 예를 들어 (())) 이때 i=6, dp[5]=4), dp[i-dp[i-1]-1], 즉 이전 합법적인 줄의 앞줄을 찾아야 한다. (만약 (, dp[i]=2+dp[i-1], 새로 읽은 줄의) 앞쪽은 (합법적인 줄도 아니고 한가한 줄도 아니다) 틈이 열을 구성할 수 없다. dp[i]=0은 변하지 않았다
괄호 동동
Time Limit: 1000MS Memory limit: 65536K
제목 설명
"("또는 ")"문자열만 포함하는 문자열str를 보여 줍니다!문자열의 길이는 100W보다 작습니다!최장 합법 문자열 및 합법 문자열의 개수를 구합니다!!
올바른 문자열의 형식은 다음과 같습니다.
1. “()”
2. “(())()”
3. “(()(()))”
비합법적인 상황은 다음과 같다.
1. “)(”
2. “(()”
3. “(()))(”
4.......
입력
각 그룹은 문자열 행으로 구성된 여러 그룹의 테스트 데이터를 입력합니다.
출력
각 그룹의 테스트 데이터에 대해 최장 합법적인 하위 문자열과 합법적인 하위 문자열의 개수를 출력한다(최장 합법적인 하위 문자열이 0이면 0 1)!
샘플 입력
))(
)((())))(()())샘플 출력
0 1
6 2#include<stdio.h>
#include<string.h>
char str[1000015];
int dp[1000015];
int ans,num;
int main()
{
while(scanf("%s",str)!=EOF)
{
int len=strlen(str);
dp[0]=0;
ans=0;num=1;
for(int i=1; i<len; i++)
{
dp[i]=0; //(() ) <===i
if( i-dp[i-1]-1>=0 && str[i]==')' && str[i-dp[i-1]-1]=='(' )
{
dp[i]=dp[i-1]+2;
if(i-dp[i-1]-2>=0&&dp[i-dp[i-1]-2])//(())()
{
dp[i]+=dp[i-dp[i-1]-2];
}
}
if(ans<dp[i]) // ， 1
{
ans=dp[i];
num=1;
}
else if(ans==dp[i]&&ans) //
num++;
}
printf("%d %d
",ans,num);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
