NENU 博士的化学元素发音问题

某天，博士突然对化学无比狂热，对化学的无比狂热使得他认为自己说的每一句话都应该由元素名称组成的，例如：“I Am CLaRa”（I是碘，Am是镅，C是碳，La镧，Ra是镭），“InTeRnAtIONAl”。但是有些词他是不能说的，例如“collegiate”, “programming” and “contest”。

现在给你一些单词，博士希望你确定这些单词是他是否能说，如果能输出YES，不能输出NO。

 

Input

第一行T表示数据组数。

下面T行每行一个字符串，表示博士询问的词语。长度不超过5W

附录

"H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar","K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br","Kr","Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te","I","Xe","Cs","Ba","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn","Fr","Ra","Rf","Db","Sg","Bh","Hs","Mt","Ds","Rg","Cn","Fl","Lv","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm","Yb","Lu","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm","Md","No","Lr"

Output

T行，每行为YES或者NO。

Sample Input

4

international

collegiate

programming

Contest

Sample Output

YES

NO

NO

NO 

 

 

一道不错的DP题，分为几种情况：

1.单字母元素(i)为真：  需要满足条件是：(第i号字母为单元素+第i-1号字母为真)

2.双字母元素(i)为真：  需要满足条件是：(i-1号字母和i号字母组合为元素+第i-2号字母为真)

 

注意，双字母元素的情况我们是令第二个字母为真。

 

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;

char map[115][3]={"h","he","li","be","b","c","n","o","f","ne","na","mg","al","si","p","s","cl","ar",
"k","ca","sc","ti","v","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb",
"sr","y","zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","i","xe","cs","ba",
"hf","ta","w","re","os","ir","pt","au","hg","tl","pb","bi","po","at","rn","fr","ra","rf","db",
"sg","bh","hs","mt","ds","rg","cn","fl","lv","la","ce","pr","nd","pm","sm","eu","gd","tb","dy",
"ho","er","tm","yb","lu","ac","th","pa","u","np","pu","am","cm","bk","cf","es","fm","md","no","lr"};
char word[50001];
int can[1000]={0},dp[50001];

int trans(char s[3])
{
	if(s[1]==0)
		return s[0]-'a';
	return s[0]-'a'+(s[1]-'a'+1)*26;

}

int main()
{
	int T;
	memset(can,0,sizeof(can));
	for(int i=0;i<114;i++)
		can[trans(map[i])]=1;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",word);
		int len=strlen(word);
		memset(dp,0,sizeof(dp));
		for(int i=0;i<len;i++)
			if(word[i]<'a')
				word[i]=word[i]+32;
		char t[3]={0};
		t[0]=word[0];
		if(can[trans(t)])
			dp[0]=1;
		t[0]=word[1];
		if(can[trans(t)] && dp[0])
			dp[1]=1;
		t[0]=word[0];
		t[1]=word[1];
		if(can[trans(t)])
			dp[1]=1;
		for(int i=2;i<len;i++)
		{
			char t[3]={0};
			t[0]=word[i];
			if(can[trans(t)] && dp[i-1])
			dp[i]=1;
			t[0]=word[i-1];
			t[1]=word[i];
			if(can[trans(t)] && dp[i-2])
			dp[i]=1;
		}
		if(dp[len-1])
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}