URAL 1183 Brackets Sequence DP 경로 출력
(1) 공백 합법
(2) S가 적법하면 (S), [S]가 적법하다
(3) A, B가 적법하면 AB가 적법하다
아이디어:
dp[i][j]를 s(i, j)로 설정한 후 합법적인 문자열의 길이나 추가할 문자의 개수, 상태 이동:
(1) s[i]와 s[j]가 일치하면 dp[i, j]=dp[i+1, j-1].
(2) 일치하지 않으면 s(i, j)를 s(i, k)와 s(k+1, j)로 나누고, 구분한 후 dp[i, j]=dp[i, k]+dp[k+1, j]로 나누고, 두 개의 서브열이 일치하는 괄호 수가 가장 많으면 추가할 문자가 가장 적다. 즉, dp[i, k+1]+dp[k+1, j]가 가장 작고, k는 유사분단점, s(i, k)와 s(k+1, j)는 각각 출력할 수 있기 때문에 [dpi, j]=dpi(k+1, j], [dpi], k+1,
종속 관계:
dp[i,j]를 구하려면 먼저 [i,k][k,j]를 구해야 한다. 즉, 큰 구간은 작은 구간에 의존하기 때문에 구간의 길이가 가장 작은 것부터 옮겨야 한다.동네를 다 훑어보려면 0부터 시작점을 훑어봐야 한다.그래서
for len = 2 to n
for start = 0 to n-1
， k
：
dp[i][i] ， dp[i,i]=1
s s ， 。s[i,j] dp[i,j] ， ：
i>j，
i==j， ， "()" "[]"
i<j， ，
s[i] s[j] ， s(i+1,j-1) ， output(s[i]); output(i+1,j-1); output(j)；
s[i] s[j] ， dp[i,k] k ，(i,k) (k+1,j) ， pos[i,j] k， ， output(i,k); output(k+1,j)
：
1： dp[][] ，dp[i][i]=1，pos=-1。
2： dp[i][j]， pos 。
：
int dp[110][110],pos[110][110];
void DFSprint(int l,int r) //
{
if(l>r) return ;
if(l==r){
if(s[l]=='('||s[l]==')') cout << "()" ;
else cout << "[]" ;
}
else if(pos[l][r]==-1){
cout << s[l]; DFSprint(l+1,r-1); cout << s[r];
}
else{
DFSprint(l,pos[l][r]); DFSprint(pos[l][r]+1,r);
}
}
int main()
{
cin >> s ;
memset(dp,inf,sizeof(dp));
memset(pos,-1,sizeof(pos));
int len = s.size();
for(int i=0;i<len;++i)
dp[i][i]=1,dp[i+1][i]=0;
for(int length=1; length<len; ++lenght){
for(int start=0; start+length<len; ++start){
dp[i][j]=len+1; // max
// s[i] s[j]
if( (s[i]=='('&&s[j]==')') || (s[i]=='['&&s[j]==']'))
dp[i][j]=min(dp[i][j], dp[i+1][j-1]);
//
for(int k=i;k<j;++k){
if(dp[i][j] > dp[i][k]+dp[k+1][j]){
dp[i][j] = dp[i][k]+dp[k+1][j];
pos[i][j] = k;
}
}
}
}
DFSprint(0,len-1);
cout << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
