脱水缩合

【题目描述】 fqk 退役后开始补习文化课啦， 于是他打开了生物必修一开始复习蛋白质，他回想起了氨基酸通过脱水缩合生成肽键，具体来说，一个氨基和一个羧基会脱去一个水变成一个肽键。于是他脑洞大开，给你出了这样一道题： fqk 将给你 6 种氨基酸和 m 个脱水缩合的规则，氨基酸用'a ' , ' b' , ' c' , 'd ' , ' e' , 'f '表示，每个规则将给出两个字符串 t s, ，其中 | s| =2, |t | =1，表示 s 代表的两个氨基酸可以通过脱水缩合变成 t 。然后请你构建一个长度为 n ,且仅由 'a ' , ' b' , 'c ' , 'd ' , ' e' , ' f'  构成的氨基酸序列，如果这个序列的前两个氨基酸可以进行任意一种脱水缩合， 那么就可 以脱水缩合，脱水缩合后序列的长度将 1  ，这样如果可以进行 1  n 次脱水缩合，最终序列的长度将变为 1 ，我们可以认为这是一个蛋白质，如果最后的蛋白质为 ' 'a ， 那么初始的序列就被称为一个好的氨基酸序列。 fqk 想让你求出有多少好的氨基酸序列。 注：题目描述可能与生物学知识有部分偏差（即氨基酸进行脱水缩合后应该是肽链而不是新的氨基酸），请以题目描述为准。 【输入格式】 第一行两个整数 n, q。 接下来 q 行，每行两个字符串 t s, ，表示一个脱水缩合的规则。 【输出格式】 一行，一个整数表示有多少好的氨基酸序列。 【输入样例】 3 5 ab a cc c ca a ee c ff d 【输出样例】 4 【样例解释】 一共有四种好的氨基酸序列，其脱水缩合过程如下： "abb"--> "ab"--> "a" "cab" -->"ab"--> "a" "cca" -->"ca"--> "a" "eea" -->"ca" -->"a" 【数据范围】 对于 100% 的数据，2<=n<=6, q<=36

#include<cstdio> #include<iostream> using namespace std; char q[7],a[40],b[40],c[40]; int n,m,ans,flag; void Dfs(int t) { if(flag)return; if(t==n&&q[t]=='a') {flag=1;return;} for(int i=1;i<=m;i++) if(a[i]==q[t]&&b[i]==q[t+1]) { q[t+1]=c[i]; Dfs(t+1); q[t+1]=b[i]; } } void check() { flag=0; Dfs(1); if(flag)ans++; } void dfs(int t) { if(t>n){check();return;} for(int i=0;i<=5;i++) { q[t]=char(i+'a'); dfs(t+1); } } int main() { //freopen("jh.in","r",stdin); freopen("merge.in","r",stdin); freopen("merge.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i]; dfs(1); printf("%d",ans); return 0; }

 

。数据存在梯度。【时空限制】对于每个测试点，时间限制为 s 2 ,空间限制为 MB 512 。