首页 > ACM题库 > HDU-杭电 > HDU 3109-Worms [解题报告]HOJ
2014
03-02

HDU 3109-Worms [解题报告]HOJ

Worms

问题描述 :

Biologists are studying a certain, interesting kind of worm. Each worm can be seen as a line of cells of different types. When a worm is born, it only consists of a single cell. Every day, exactly 1 cell of the entire worm will grow and change into 2 cells. It is rather easy to determine the age of any such worm, since it’s simply one less than the number of cells the worm has.

During a worm’s growth, a cell does not change into any 2 arbitrary cells; each worm has a set of “growth rules" (encoded in its DNA) that it obeys. A growth rule can be expressed as A –> BC , where A , B and C are uppercase letters (with letters A-T), representing different types of the worm’s cells. The rule A –> BC means that in one day, any single cell A can be grown into the 2 adjacent cells BC , in that order. Note that the rule I –> JK is different from the rule I –> KJ . Different worms may have a different set of growth rules.

The worms have now thrown the scientists for a loop. Due to some unknown reason, some worms have mutated into a new kind of specimen. This new kind of worm has the exact same properties, except that during its growth, multiple parts of its body can grow at the same time. That is, every day any (at least one, at most all) of its cells can grow; each cell that grows will grow into exactly 2 cells (obeying growth rules similar to their older cousins).

As a result of the mutation, it is no longer trivial to determine the age of a worm. In fact, the exact age of some worms cannot be determined. As a simple example, if a worm has growth rules: A –> BC , B –> AC , C –> AB , and the worm’s current cell structure is ACAB , the worm can be either 2 or 3 days old ( A –> BC –> ACAB , or A –> BC –> ACC –> ACAB ). Your task is to find out the youngest possible age of any given mutated worm.

输入:

There will be multiple worms for examination in the input. Each worm’s data set begins with an integer N ( 1<=N<=80 ), the number of growth rules. The next N lines each contain 3 uppercase letters (with letters A-T), representing a growth rule for the current worm. The 1st cell can grow into (and be replaced by) the 2nd and 3rd cells, in order, during the growth process. That is, the line:

ABC

means A –> BC is a growth rule for the current worm.

The next (and last) line of each worm’s data set contains a string of uppercase letters (with letters A-T). This line represents the current cell structure of the worm. Every worm in the input will have at least 1 and at most 50 cells.

The last worm will be followed by a line with a single 0.

输出:

There will be multiple worms for examination in the input. Each worm’s data set begins with an integer N ( 1<=N<=80 ), the number of growth rules. The next N lines each contain 3 uppercase letters (with letters A-T), representing a growth rule for the current worm. The 1st cell can grow into (and be replaced by) the 2nd and 3rd cells, in order, during the growth process. That is, the line:

ABC

means A –> BC is a growth rule for the current worm.

The next (and last) line of each worm’s data set contains a string of uppercase letters (with letters A-T). This line represents the current cell structure of the worm. Every worm in the input will have at least 1 and at most 50 cells.

The last worm will be followed by a line with a single 0.

样例输入:

3
ABC
BAC
CAB
ACAB
1
AAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
2
PAA
AAA
AAAAAAAAAAAAAAAP
1
BAB
AAAAAAB
0

样例输出:

2
6
-1
6

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
vector<int> Org[30][30];
char Trs[90][5];
char st[60];
int f[60][60][30];
int Max2(int a,int b)
{
 return a>b?a:b;
}
int main()
{
 int N,i,j,k,t,L,Ans;
 for (;;)
 {
 scanf("%d",&N);
 if (N==0) break;
 ///f[i][j][ch] refers from i to j cost min
 ///f[i][j][ch]=min{max{f[i][k][tch1],f[k+1][j][tch2]}}
 for (i=0;i<='T'-'A';i++)
 for (j=0;j<='T'-'A';j++)
 Org[i][j].clear();
 for (i=0;i<N;i++)
 {
 scanf("%s",Trs[i]);
 Org[Trs[i][1]-'A'][Trs[i][2]-'A'].push_back(Trs[i][0]-'A');
 }
 scanf("%s",st);
 L=strlen(st);
 memset(f,-1,sizeof(f));
 f[0][0][st[0]-'A']=0;
 for (i=1;i<L;i++)
 {
 f[i][i][st[i]-'A']=0;
 if (Org[st[i-1]-'A'][st[i]-'A'].size()!=0)
 {
 for (j=0;j<Org[st[i-1]-'A'][st[i]-'A'].size();j++)
 f[i-1][i][Org[st[i-1]-'A'][st[i]-'A'][j]]=1;
 }
 }
 for (j=2;j<L;j++)
 for (i=0;i+j<L;i++)
 {
 for (t=0;t<N;t++)
 {
 for (k=i;k<i+j;k++)
 if (f[i][k][Trs[t][1]-'A']!=-1 && f[k+1][i+j][Trs[t][2]-'A']!=-1 && (f[i][i+j][Trs[t][0]-'A']==-1 || f[i][i+j][Trs[t][0]-'A']>Max2(f[k+1][i+j][Trs[t][2]-'A'],f[i][k][Trs[t][1]-'A'])+1))
 f[i][i+j][Trs[t][0]-'A']=Max2(f[k+1][i+j][Trs[t][2]-'A'],f[i][k][Trs[t][1]-'A'])+1;
 }

 }
 Ans=-1;
 for (i=0;i<='T'-'A';i++)
 if (Ans==-1 || (f[0][L-1][i]!=-1 && Ans>f[0][L-1][i]))
 Ans=f[0][L-1][i];
 printf("%d\n",Ans);
 }
}

  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  4. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish