本文正體字版由OpenCC轉換
這是一個思路新穎的動態規劃問題，一看道題的時候看起來像搜索，一時沒有想出動態規劃。但是隻要把思路變一下，要求給定的字串最少由幾個S變換而成，每個自串能合成什麼。
假設我們已經知道了，給定的串S，從第i位到第j位，能夠合成的單個字母的集合，用G[i,j]表示，那麼我們可以定義
F[i,j](1<=i,j<=L L爲S長度)表示串S從第i位到第j位能夠合成的S的最小個數
狀態轉移方程
F[i,j]=Min { F[i,k]+F[k+1,j] | i<=k<=j-1, 1 | ‘S’ 屬於 G[i,j] }
邊界條件
F[i,j]=∞
結果就是 F[1,L]
現在只需求出G[i,j]即可。我們定義H[A,B]爲字母A,B能夠合成的字母的集合，對於樣例 SAB SBC SAA ACA BCC CBC 有 H[‘A’,‘B’]={‘S’} H[‘B’,‘C’]={‘S’,‘C’} H[‘A’,‘A’]={‘S’} H[‘C’,‘A’]={‘A’} H[‘C’,‘C’]={‘B’}
然後G[i,j]依然可以用動態規劃求出。
狀態轉移方程
G[i,j]=Union{H[A,B] | A 屬於 G[i,k] 且 B 屬於 G[k+1,j] 且 i<=k<=j-1}
上式表示從G[i,k]和G[k+1,j]兩個集合中，我們各取一個元素A，B，代表S[i,k]變換而成的A和S[k+1,j]變換而成的B，將A,B合成G[i,j]的一個元素。
邊界條件 G[i,j]=Ø (1<=i,j<=L , i!=j) G[i,i]={S[i]}
以上的動態規劃的方法是我第一次使用的，編程的時候要格外注意細節。關於集合的運算，我們可以用兩個32位整型數保存每個字母的狀態，用位運算的方法求是否包含每個元素，按位求或就是並集。
#include <iostream>
using namespace std;
class tSet
{
public:
unsigned int P;
tSet():P(0){}
bool Contain(int k)
{
return (P >> (k))&1;
}
void Union(tSet &k)
{
P |=k.P;
}
void Union(int k)
{
P |=1 << (k);
}
};
const int Target='S'-'A';
const int MAX_L=101;
const int INF=0x7FFFFFF;
int N,M,L,Ans;
char S[MAX_L];
tSet H[26][26];
tSet G[MAX_L][MAX_L];
int F[MAX_L][MAX_L];
void init()
{
int i,c,a,b;
freopen("gen.in","r",stdin);
freopen("gen.out","w",stdout);
scanf("%dn",&M);
for (i=1;i<=M;i++)
{
gets(S);
c=S[0]-'A';
a=S[1]-'A';
b=S[2]-'A';
H[a][b].Union(c);
}
scanf("%dn",&N);
}
void solve()
{
int i,j,k,a,b;
for (i=1;i<=L;i++)
{
for (j=1;j<=L;j++)
{
G[i][j].P=0;
}
G[i][i].Union((int)S[i-1]);
}
for (i=L;i>=1;i--)
{
for (j=i+1;j<=L;j++)
{
for (k=i;k<=j-1;k++)
{
for (a=0;a<26;a++)
{
for (b=0;b<26;b++)
{
if (G[i][k].Contain(a) && G[k+1][j].Contain(b))
{
G[i][j].Union(H[a][b]);
}
}
}
}
}
}
for (i=1;i<=L;i++)
{
for (j=1;j<=L;j++)
{
F[i][j]=INF;
}
}
for (i=L;i>=1;i--)
{
for (j=i;j<=L;j++)
{
if (G[i][j].Contain(Target))
{
F[i][j]=1;
}
else
{
for (k=i;k<=j-1;k++)
{
if (F[i][k]+F[k+1][j]<F[i][j])
{
F[i][j]=F[i][k]+F[k+1][j];
}
}
}
}
}
Ans=F[1][L];
}
int main()
{
init();
for (int i=1;i<=N;i++)
{
gets(S);
for (L=0;S[L];L++)
{
S[L]-='A';
}
solve();
if (Ans==INF)
printf("NIEn");
else
printf("%dn",Ans);
}
return 0;
}
基因串
基因串是由一串有限長度的基因所組成的，其中每一個基因都可以用26個英文大寫字母中的一個來表示，不同的字母表示不同的基因類型。一個單獨的基因可以生長成爲一對新的基因，而可能成長的規則是通過一個有限的成長規則集所決定的。每一個成長的規則可以用三個大寫英文字母A1A2A3來描述，這個規則的意思是基因A1可以成長爲一對基因A2A3。
我們用大寫字母S來表示一類被稱作超級基因的基因。因爲每一個基因串都是由一串超級基因根據給出的規則所成長出來的。
任務：
請寫一個程序：
* 從文本文件中讀入有限條成長的規則和一些我們想要得到的基因串；
* 對於每個基因串，試判斷它是否可以由一個有限長度的超級基因串成長得出。如果可以，那麼請給出可成長爲該基因串的最短超級基因串的長度；
* 把結果輸出到文本文件中。
輸入格式：
在文本文件GEN.IN的第一行包括一個整數n，1 <= n <= 10000。以下的n行中每行都包括一個成長的規則，每個規則由三個大寫英文字母組成。
在該文件的第n+1行包括一個整數k，1 <= k <= 10000。以下的k行中每行都有一個基因串。每個基因串都是一個長度不超過100的大寫字符串。
輸出格式：
在文件的第i（應共k行）行中你應該輸出入下內容：
一個正整數，表示成長爲改基因串所需的最短的超級基因串的長度；
或一個單詞NIE（波蘭語的“否”），如果說無法由超級基因串成長成爲該基因串。
樣例：
輸入
6
SAB
SBC
SAA
ACA
BCC
CBC
3
ABBCAAABCA
CCC
BA
輸出
3
1
NIE
上次修改時間 2017-02-03