动态规划或者记忆化深搜。
View Code
1 #include <stdio.h> 2 #define N 1005 3 char a[N],b[N],c[N][N]; 4 int n; 5 char dfs(int left,int right) 6 { 7 int k=right-left+1; 8 char f1=0,f2=0; 9 if(left==0&&right==n-1) return 1; 10 if(c[left][right]!=-1) return c[left][right]; 11 if(left>0&&b[k]==a[left-1]) f1=dfs(left-1,right); 12 if(right<n-1&&b[k]==a[right+1]) f2=dfs(left,right+1); 13 if(f1+f2) return c[left][right]=1; 14 else return c[left][right]=0; 15 } 16 int main() 17 { 18 int i,j,yes; 19 while(~scanf("%d",&n)) 20 { 21 for(i=0;i<n;i++) scanf("%d",&a[i]); 22 for(i=0;i<n;i++) scanf("%d",&b[i]); 23 yes=0; 24 memset(c,-1,sizeof(c)); 25 for(i=0;i<n;i++) 26 { 27 if(a[i]!=b[0]) continue; 28 if(dfs(i,i)) 29 { 30 yes=1; 31 break; 32 } 33 } 34 if(yes) printf("YES\n"); 35 else printf("NO\n"); 36 } 37 return 0; 38 }