uva 10723 uva 10723 Cyborg Genes는 s1, s2의 가장 짧은 합렬 즉 합렬의 구성 방법수를 구한다
dp[i][j]메모리 s1[i]와 s2[j]의 가장 짧은 합성 길이, dp[i][0]=dp[0][i]=i 초기화
1. s1[i]=s2[j]일 때 dp[i][j]=dp[i-1][j-1];
2. 그렇지 않으면 dp[i][j]=min(dp[i-1][j], dp[i][j-1]).
f[i][j]메모리 s1[i]와 s2[j]가 가장 짧은 열을 구성하는 방법, 초기 f[i][0]=f[0][i]=1,
1. 만약에 s1[i]=s2[j]는 마지막에만 놓을 수 있고 f[i][j]=f[i-1][j-1];
2. 서로 다르면 이때 새로 추가된 s1[i], s2[j]의 배치는 두 가지 상황이 있는데 하나는 s1[i]가 s2[j]의 뒤에 놓인 (f[i-1][j]), 다른 하나는 s1[i]가 s2[j]의 앞에 놓인 (f[i][j-1]), 즉 새로 추가된 마지막 문자의 앞이 s1[i]인지 s2[j]인지 고려해야 한다. 이때 어떤 배치법이 가장 작은 길이의 배치법인지 고려해야 한다. 만약에 s2[j]가 공공 문자열에 참여할 수 있다면 마지막에 놓인 s1[i]만 놓을 수 있다는 것을 알 수 있다.마찬가지로 s1[i]가 공공 문자열에 참여하면 s2[j]만 마지막에 놓을 수 있고 s1[i]와 s2[j]가 공공 문자열에 참여했는지 여부는 dp[i][j-1]과 dp[i-1][j]에서 반영할 수 있다. 만약에 s1[i]가 공공 문자열에 참여했는데 s2[j]가 없으면 dp[j][j-1]
#include<stdio.h>
#include<string.h>
char s1[50],s2[50];
int dp[50][50],f[50][50];
int l1,l2;
int min(int a,int b)
{
return a>b?b:a;
}
int main()
{
int i,j,k,l,m,n;
scanf("%d",&l);
for(k=1;k<=l;k++)
{
scanf("%s%s",s1+1,s2+1);
l1=strlen(s1+1);
l2=strlen(s2+1);
for(i=0;i<50;i++)
{
dp[0][i]=dp[i][0]=i;//
f[0][i]=f[i][0]=1; //
}
for(i=1;i<=l1;i++)
{
for(j=1;j<=l2;j++)
{
if(s1[i]==s2[j])
{
dp[i][j]=dp[i-1][j-1]+1;
f[i][j]=f[i-1][j-1];
}
else
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
if(dp[i-1][j]==dp[i][j-1])
f[i][j]=f[i-1][j]+f[i][j-1];
else if(dp[i-1][j]<dp[i][j-1])
f[i][j]=f[i-1][j];
else
f[i][j]=f[i][j-1];
}
}
}
printf("Case #%d: %d %d
",k,dp[l1][l2],f[l1][l2]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
