CF1331F Elementary!

题意

给你字符串 $s(1\le s\le 10)$s(1≤s≤10)，判断是否为元素周期表里的大写元素。

思路

由Elementary
结合题目中样例HOMELES DOCTOR WASTON先把题意得出。
然后再打一张化学元素的表。（dbqwsdd）

这篇博客主要是让自己知道这样的匹配有两种做法，一个是DP，一个是DFS。

• 初始化 $f\left[0\right]=true$f[0]=true
  DP递推式： $f[i+c.size(\left)\right]=true\left(f\right[i]=trueandt.substr(i,c.size\left(\right))=c)$f[i+c.size()]=true(f[i]=true  and  t.substr(i,c.size())=c)
• DFS就匹配每次现在的位置然后递归匹配未匹配的位置

DP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

vector<string>v{ "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","LA","CE","PR","ND","PM","SM","EU","GD","TB","DY","HO","ER","TM","YB","LU","HF","TA","W","RE","OS","IR","PT","AU","HG","TL","PB","BI","PO","AT","RN","FR","RA","AC","TH","PA","U","NP","PU","AM","CM","BK","CF","ES","FM","MD","NO","LR","RF","DB","SG","BH","HS","MT","DS","RG","CN","NH","FL","MC","LV","TS","OG" };
string t;
bool flag=false;

void DP(){
	vector<bool>f(t.size()+1);
	f[0]=true;
	for(int i=0;i<t.size();i++){
		if(f[i]){
			for(string c:v){
				if(t.substr(i,c.size())==c) f[i+c.size()]=true;
			}
		}
	}
	cout<<(f.back()?"YES":"NO")<<'\n';
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	DP();
	return 0;
}

DFS

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

vector<string>v{ "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","LA","CE","PR","ND","PM","SM","EU","GD","TB","DY","HO","ER","TM","YB","LU","HF","TA","W","RE","OS","IR","PT","AU","HG","TL","PB","BI","PO","AT","RN","FR","RA","AC","TH","PA","U","NP","PU","AM","CM","BK","CF","ES","FM","MD","NO","LR","RF","DB","SG","BH","HS","MT","DS","RG","CN","NH","FL","MC","LV","TS","OG" };
string t;
int len;
bool flag=false;

void dfs(int k){
	for(int i=0;i<v.size();i++){
		if(t.compare(k,v[i].size(),v[i])==0){
			if(k+v[i].size()>=len){
				flag=true;
				return;
			}
			dfs(k+v[i].size());
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;len=t.size();
	dfs(0);
	if(flag) cout<<"YES";
	else cout<<"NO";
	return 0;
}