Poj 2192 Zipper
사고방식:DP, 2차원 그룹 dp[][], dp[i][j]는str1의 전 i 문자가str2의 전 j 문자와str의 전 i+j 문자를 구성할 수 있는지를 나타낸다.또한 i=0 또는 j=0은 빈 문자열을 표시하므로 dp를 초기화할 때 주의해야 한다.증명 가능: dp[i-1][j](dp[i][j]위 한 칸)과 dp[i][j-1](dp[i][j]왼쪽 한 칸)이 모두 0이면 dp[i][j]는 0이다.dp[i-1][j](dp[i][j]위 칸)이 1이고 왼쪽 자모가str[i+j]일 때, 또는 dp[i][j-1](dp[i][j]왼쪽 칸)이 1이고 위 자모가str[i+j]일 때 dp[i][j]가 1이다.
#include <stdio.h>
#include <string.h>
char str1[220];
char str2[220];
char str[420];
int dp[220][220];
int main()
{
int t,i,j,k,ctr;
int length1,length2;
scanf("%d",&t);
for (ctr=1;ctr<=t;ctr++) {
scanf("%s%s%s",&str1,&str2,&str);
length1=strlen(str1);
length2=strlen(str2);
dp[0][0]=1;
// 0
for (i=1;i<=length1;i++) {
if (dp[0][i-1]==1&&str1[i-1]==str[i-1])
dp[0][i]=1;
else
dp[0][i]=0;
}
// 0
for (i=1;i<=length2;i++) {
if (dp[i-1][0]==1&&str2[i-1]==str[i-1])
dp[i][0]=1;
else
dp[i][0]=0;
}
for (i=1;i<=length2;i++) {
for (j=1;j<=length1;j++) {
dp[i][j]=0;
}
}
// dp
for (i=1;i<=length2;i++) {
for (j=1;j<=length1;j++) {
if ((dp[i][j-1]==1&&str1[j-1]==str[i+j-1])||(dp[i-1][j]==1&&str2[i-1]==str[i+j-1]))
dp[i][j]=1;
}
}
printf("Data set %d: ",ctr);
if (dp[length2][length1]==1)
printf("yes
");
else
printf("no
");
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
