fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <ctime>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. #include <vector>
  12. #define REP(I,A,B) for(int I=A,END=B;I<=END;I++)
  13. #define REPD(I,A,B) for(int I=A,END=B;I>=END;I--)
  14. #define RI(X) scanf("%d",&X)
  15. #define RS(X) scanf("%s",X)
  16. #define GCH getchar()
  17. #define PCH(X) putchar(X)
  18. #define MAX(A,B) (((A)>(B))?(A):(B))
  19. #define MIN(A,B) (((A)<(B))?(A):(B))
  20. #define MS(X,Y) memset(X,Y,sizeof(X))
  21. #define MC(X,Y,var,len) memcpy((X),(Y),sizeof(var)*(len))
  22. #define debug(...) fprintf(stderr,__VA_ARGS__)
  23. #define MAXN 105
  24. using namespace std;
  25. char str[MAXN]={0};
  26. int len=0;
  27. int f[MAXN]={0};
  28. int g[27][MAXN][MAXN]={0};
  29. struct trans
  30. {
  31.   int ch1,ch2;
  32. };
  33. vector <trans> change[27];
  34. int size[27]={0};
  35. int n;
  36. void open()
  37. {
  38.   freopen("gen.in","r",stdin);
  39.   freopen("gen.out","w",stdout);
  40. }
  41. void close()
  42. {
  43.   fclose(stdin);
  44.   fclose(stdout);
  45. }
  46. void init_dynamic()
  47. {
  48.   MS(g,0);
  49.   REP(i,0,len)
  50.     g[str[i]-'A'+1][i][i]=1;
  51.   int j,ch1,ch2;
  52.   REP(l,1,len)
  53.     REP(i,0,len-l)
  54.     {
  55. 	   j=i+l;
  56. 	   REP(ch,1,26)
  57. 	   {
  58. 	     REP(k,0,size[ch])
  59. 	     {
  60. 		   ch1=change[ch][k].ch1;
  61. 		   ch2=change[ch][k].ch2;
  62. 		   REP(kk,i,j)
  63. 		     if (g[ch1][i][kk]==1 && g[ch2][kk+1][j]==1)
  64. 		     {
  65. 			   g[ch][i][j]=1;
  66. 			   break;
  67. 		     }
  68. 		   if (g[ch][i][j])
  69. 		     break;
  70. 		 }
  71. 	   }
  72. 	}
  73. }
  74. #define S 19
  75. void dynamic()
  76. {
  77.   MS(f,0);
  78.   REP(i,0,len)
  79.   {
  80.     f[i]=g[S][0][i];
  81.     if (f[i]==0)
  82.       f[i]=101;
  83.   }
  84.   REP(i,0,len-1)
  85.    REP(j,1,len)
  86.      if (f[i]!=101)
  87.      {
  88. 	   if (g[S][i+1][j]==1)
  89. 	     if (f[j]>f[i]+1)
  90. 	       f[j]=f[i]+1;
  91. 	 }
  92.   if (f[len]!=101)printf("%d\n",f[len]);
  93.   else printf("NIE\n");
  94. } 
  95. void init()
  96. {
  97.   RI(n);
  98.   char ch[3];
  99.   GCH;
  100.   int ch1,ch2,ch3;
  101.   REP(i,1,n)
  102.   {
  103.     RS(ch);    
  104.     ch1=ch[0]-'A'+1,ch2=ch[1]-'A'+1,ch3=ch[2]-'A'+1;
  105.     change[ch1].push_back((trans){ch2,ch3});
  106.     size[ch1]++;
  107.   }
  108.   REP(i,1,26)
  109.     size[i]--;
  110.   //REP(i,1,10)
  111.   {
  112.     RS(str);
  113.     len=strlen(str)-1;
  114.     init_dynamic();//预处理数组 
  115. 	dynamic();//
  116.   }
  117. }
  118. int main()
  119. {
  120.   open();
  121.   init();
  122.   close();
  123.   return 0;
  124. }
  125.  
Success #stdin #stdout 0s 4304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wTom40
POI9706 ZJOI2005 Genotype
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!