hdu 5282 Senior's String 동적 계획
x, y 두 꿰미,
x의 몇 개의 서열이 y의 서열에 나타나고 x의 서열은 길이가 x와 y의 가장 긴 서열의 길이를 만족시킨다
dp[i][j]로 x의 i 위치와 y의 j 위치의 가장 긴 공통 서열 길이를 나타낸다.dp[i][j] 구하기
그리고num[i][j]는 x의 전 i자 구성의 길이가 dp[i][j]인 하위 서열에서 y의 전 j자 구성의 길이가 dp[i][j]인 하위 서열에 얼마나 많은지 나타낸다.
만약에 dp[i][j]=dp[i-1][1]이면 x의 전 i-1 문자는 dp[i][j]의 하위 서열을 구성하고 y의 전 j 문자가 하위 서열을 구성하는 데 나타날 수 있음을 나타낸다.
그럼num[i][j]=num[i-1][j]
x의 i번째 문자로 서열을 구성할지, x의 i번째 문자로 일치하는지, y의 전 j 문자 중 x[i]와 같고, 가장 오른쪽에 있는 문자 y[u]와 일치하는지 고려
만약 dp[i-1][u-1]==dp[i][j]-1을 만족시킨다면 현재 조건에서 x[i]로 새로운 서열을 구성할 수 있고 길이=dp[i][j]를 만족시킬 수 있으며 y 전 j 문자로 구성된 서열에 있다.
그럼num[i][j]+=num[i-1][u-1]
정답은num[len1][len2]입니다.
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int mod = 1000000007;
int dp[1001][1001];
int num[1001][1001];
char w1[1011];
char w2[1011];
int c[1001][26];
int main(){
int t = 0,u,p;
scanf("%d",&t);
while(t--){
scanf("%s%s",w1+1,w2+1);
memset(dp,0,sizeof(dp));
memset(num,0,sizeof(num));
int len1 = strlen(w1+1);
int len2 = strlen(w2+1);
memset(c,0,sizeof(c));
for(int i = 1;i <= len2; i++){
for(int j = 0;j < 26;j++)
c[i][j] = c[i-1][j];
c[i][w2[i]-'a'] = i;
}
for(int i = 0;i <= len2; i++)
num[0][i] = 1;
for(int i = 0;i <= len1; i++)
num[i][0] = 1;
for(int i = 1;i <= len1; i++){
for(int j = 1;j <= len2; j++){
if(w1[i] == w2[j])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
if(dp[i-1][j] == dp[i][j])
num[i][j] = num[i-1][j];
u = c[j][w1[i]-'a'];
if(dp[i-1][u-1] == dp[i][j]-1 && u > 0)
num[i][j] += num[i-1][u-1];
if(num[i][j] >= mod)
num[i][j] -= mod;
}
}
printf("%d
",num[len1][len2]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.