HDUOJ 4632 2013 멀티 스쿨 4차전 1문제
제목: 문자열의 회문 서열의 개수를 구하십시오.
1001
임의의 회문 서열의 끝을 맺는 두 문자가 반드시 같다는 것을 알아차리면 구간 dp를 표시하고 dp[i][j]로 원 문자열의 [i, j] 위치에 나타난 회문 서열의 개수를 표시하며 점차적인 관계가 있다.
dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]
만약 i와 j의 위치에 나타난 문자가 같다면 dp[i][j]는 dp[i+1][j-1]의 하위 서열에 이 두 문자를 더해서 회문 하위 서열을 구성할 수 있다. 즉, dp[i][j]+=dp[i+1][j-1]이다. 경계 특판에 주의하면 된다.
이상 단락은 공식 문제풀이 보고서 원어입니다. 에이~ 다교때 생각했는데 어디로 갔는지...물론 이것만으로는 부족하지만 스스로 a[i]=a[j]를 밀어야 할 때 dp[i][j]+=dp[i+1][j-1]뿐만 아니라 dp[i][j]+=1도 밀어야 한다.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[1005][1005];
int main()
{
int num=1;
char a[1005];
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",&a);
int l=strlen(a);
memset(f,0,sizeof(f));
for(int i=0;i<l;i++)f[i][i]=1;
for(int j=1;j<l;j++)
{
for(int i=j-1;i>=0;i--)
{
f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1];
if(a[i]==a[j])
{
f[i][j]+=f[i+1][j-1];
f[i][j]++;
}
f[i][j]=f[i][j]%10007;
}
}
cout<<"Case "<<num++<<": ";
cout<<(f[0][l-1]+10007)%10007<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu2457 AC 로봇 + DP사고방식: 먼저 병변의 유전자열을 Trie수로 만든 다음에 AC자동기의fail지침을 구성한다.trie에 있는 모든 끝 노드는 도착할 수 없고 할당 1은 모든 끝 노드를 가리키는 점도 도착할 수 없고 똑같이 할당한다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
