HDU 4632 Palindrome subsequence(구간 DP)

제목의 뜻

문자열을 정하고 몇 개의 회문 문자열이 있는지 묻는다. (두 문자열은 같을 수 있다).

사고의 방향

임의의 회문 서열로 두 문자가 반드시 같다는 것을 알아차리고 dp를 구간할 수 있다. dp[i][j]로 원 문자열 중 [i, j] 위치에 나타난 회문 서열의 개수를 표시하고 점차적인 관계가 있다. dp[i][j]=dp[i+1][j]+dp[j][j-1]-dp[j-1]-dp[i+1][j-1][j-1](*) 만약 i와 j 위치에 나타난 문자가 같으면 dp[i][j][j]는 j-dpi+1]에서 [j]의 서열로 구성할 수 있다.즉 dp[i][j]+=dp[i+1][j-1]입니다. 경계특판에 주의하시면 됩니다.
뭐...구간DP 발견 용척~묘~

코드


#include 
 
   
    
  
#include 
  
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #define MID(x,y) ((x+y)/2) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int dp[1003][1003]; int main(){ int t; string s; scanf("%d", &t); for (int ca = 1; ca <= t; ca ++){ cin >> s; mem(dp, 0); for (int i = 0; i <= (int)s.size(); i ++){ dp[i][i] = 1; } for (int length = 2; length <= (int)s.size(); length ++){ for (int l = 0; l + length - 1 < (int)s.size(); l ++){ int r = l + length - 1; dp[l][r] = (dp[l+1][r] + dp[l][r-1] - (length == 2?0:dp[l+1][r-1]) + 10007) % 10007; //       +10007  ？。。。      ？    ？。。。 if (s[l] == s[r]){ dp[l][r] = (dp[l][r] + (length == 2?0:dp[l+1][r-1]) + 1) % 10007; } //printf("l = %d r = %d dp = %d
", l, r, dp[l][r]); } } printf("Case %d: %d
", ca, dp[0][s.size()-1]); } return 0; }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

POJ 2442 Sequence

Sequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 4632 Palindrome subsequence(구간 DP)

제목의 뜻

사고의 방향

코드

좋은 웹페이지 즐겨찾기