首页 > 代码库 > 脱水缩合

脱水缩合

脱水缩合
(merge.c/cpp/pas)
【题目描述】
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 。

 

脱水缩合