구간DP 기본편 POJ2955-Brackets
제목은 새말이지만 가장 큰 괄호 일치수를 요구한다고 적나라하게 알려주고 DP 가자~
dp[i][j]는 구간 [i, j]의 최대 일치수를 나타낸다. 그러면 가장 중요한 상태 이동 방정식은 다음과 같다.
dp[i][j]=max(dp[i][k]+dp[k+1][j])
참, 경계부터 초기화해야지, 두 걸음으로~:
memset(dp,0,sizeof dp);
ifstr[i]==str[i+1]면: dp[i][i+1]=2 보십시오---->> 이 문자열([][]]][)은 잘 알고 있습니다
극악무도한 스티커 코드:
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[110][110];
char s[110];
bool check(int i,int j)//
{
if(s[i]=='['&&s[j]==']') return true;
if(s[i]=='('&&s[j]==')') return true;
return false;
}
int main()
{
while(scanf("%s",s)!=EOF){
if(strcmp(s,"end")==0) break;
int l=strlen(s);
memset(dp,0,sizeof dp);
for(int i=0;i<l;i++){ //
if(check(i,i+1)){
dp[i][i+1]=2;
}
}
for(int p=3;p<=l;p++){ //
for(int i=0;i<=l-p;i++){ //
int j=i+p-1;
if(check(i,j)){
dp[i][j]=dp[i+1][j-1]+2;
}
for(int k=i;k<j;k++){ //
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
cout<<dp[0][l-1]<<endl;
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
