Chemist’s vows

Chemist’s vows

题意:

 输入一个字符串，如果这个字符串可以由元素周期表的元素组成，就输出YES,反之则输出NO

思路：

 其实这个题可以用dp做，确实刚开始做的时候没想到，之前倒是做过一个类似的，这类问题，我就先叫它状态dp吧 大名叫啥还真不知道

dp状态

dp[n] 表示前n个字符能否全部由元素周期表构成，如果可以就是true，反之为false

那么我们就可以通过O(n)枚举的方法来得到状态转移方程
dp[j] = (dp[j - 1] & (字符j是否为元素符号)) | (dp[j - 2] & (字符j - 1与j是否可以构成一个元素符号))
dp[0] = true 为空串时显然可以
有了状态转移方程,我们就很好进行处理了，只需要开一个二维数组vis[i,j]表示字符i于字符j是否可以构成元素符号，当然，如果只有一个字符，j就默认为0

code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 5e4 + 5;

const char chem[120][10] =
{
	"0", "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"
};


bool vis[130][130],dp[maxn];
char str[maxn];

void init()
{
    for(int i = 1; i <= 120; i++){
        vis[chem[i][0]][chem[i][1]] = true;
    } 
}

int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--){
        memset(dp,false,sizeof dp);
        scanf("%s",str + 1);
        int len = strlen(str + 1);
        dp[0] = true;
        for(int i = 1; i <= len; i++){
            if(i > 1) dp[i] = dp[i - 2] & vis[str[i - 1]][str[i]];
            dp[i] = dp[i] | (vis[str[i]][0] & dp[i - 1]);
        }
        if(dp[len]) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}