首页 > 代码库 > UVALive 6257 Chemist's vows --一道题的三种解法（模拟，DFS，DP）
UVALive 6257 Chemist's vows --一道题的三种解法（模拟，DFS，DP）
题意：给一个元素周期表的元素符号（114种），再给一个串，问这个串能否有这些元素符号组成（全为小写）。
解法1：动态规划
定义：dp[i]表示到 i 这个字符为止，能否有元素周期表里的符号构成。
则有转移方程：dp[i] = (dp[i-1]&&f(i-1,1)) || (dp[i-2]&&f(i-2,2)) f(i,k):表示从i开始填入k个字符，这k个字符在不在元素周期表中。 dp[0] = 1
代码：
//109ms 0KB#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>using namespace std;#define N 50007string single[25] = {"h","b","c","n","o","f","k","p","s","y","i","w","u","v"};string ss[130] = {"he","li","be","ne","na","mg","al","si","cl","ar","ca","sc","ti","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","xe","cs","ba","hf","ta","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","np","pu","am","cm","bk","cf","es","fm","md","no","lr"};int vis[30][30],tag[30];int dp[N];char st[N];void init(){ memset(vis,0,sizeof(vis)); memset(tag,0,sizeof(tag)); for(int i=0;i<14;i++) tag[single[i][0]-‘a‘] = 1; for(int i=0;i<100;i++) vis[ss[i][0]-‘a‘][ss[i][1]-‘a‘] = 1;}int main(){ int t,len,i; init(); scanf("%d",&t); while(t--) { scanf("%s",st+1); len = strlen(st+1); memset(dp,0,sizeof(dp)); dp[0] = 1; for(i=0;i<len;i++) { if(dp[i]) { if(tag[st[i+1]-‘a‘]) dp[i+1] = 1; dp[i+2] |= vis[st[i+1]-‘a‘][st[i+2]-‘a‘]; } } if(dp[len]) puts("YES"); else puts("NO"); } return 0;}
解法2：DFS
搜索时循环的是元素周期表的符号个数。详见代码
代码： （306ms）
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>using namespace std;#define N 50007string ss[130] = {"h","b","c","n","o","f","k","p","s","y","i","w","u","v","he","li","be","ne","na","mg","al","si","cl","ar","ca","sc","ti","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","xe","cs","ba","hf","ta","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","np","pu","am","cm","bk","cf","es","fm","md","no","lr"};int vis[N];int len[140];char st[N];int Length;bool Tag;void init(){ int i; for(i=0;i<14;i++) len[i] = 1; for(i=14;i<114;i++) len[i] = 2;}void dfs(int u){ if(u == Length) Tag = 1; if(Tag) return; for(int i=0;i<114;i++) { int flag = 1; if(u+len[i] <= Length && !vis[u+len[i]]) { for(int j=0;j<len[i];j++) { if(ss[i][j] != st[u+j]) { flag = 0; break; } } if(flag) { vis[u+len[i]] = 1; dfs(u+len[i]); } } }}int main(){ init(); int t,i; scanf("%d",&t); while(t--) { scanf("%s",st); Length = strlen(st); memset(vis,0,sizeof(vis)); Tag = 0; dfs(0); if(Tag) puts("YES"); else puts("NO"); } return 0;}
解法3：乱搞，模拟。
分成： 单个元素存在与否，与前面匹不匹配，与后面匹不匹配，总共2^3 = 8种情况，然后O(n)扫过去，代码很长。。。
代码：（586ms）
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>using namespace std;#define N 50007string single[25] = {"h","b","c","n","o","f","k","p","s","y","i","w","u","v"};string ss[130] = {"he","li","be","ne","na","mg","al","si","cl","ar","ca","sc","ti","cr","mn","fe","co","ni","cu","zn","ga","ge","as","se","br","kr","rb","sr","zr","nb","mo","tc","ru","rh","pd","ag","cd","in","sn","sb","te","xe","cs","ba","hf","ta","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","np","pu","am","cm","bk","cf","es","fm","md","no","lr"};char st[N];int vis[N];int main(){ int t,len,i,j,k; scanf("%d",&t); while(t--) { scanf("%s",st); len = strlen(st); int flag = 1; memset(vis,0,sizeof(vis)); for(i=0;i<len;i++) { if(vis[i]) continue; string S = ""; S += st[i]; for(j=0;j<14;j++) { if(single[j] == S) break; } if(j == 14) //not single { if(i > 0 && !vis[i-1]) { S = st[i-1]+S; for(j=0;j<100;j++) { if(ss[j] == S) break; } if(j != 100) //pre match { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i] = 0; } else //back not match vis[i] = 1; } } else //pre not match { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i+1] = 1; } else //back not match { flag = 0; break; } } else { flag = 0; break; } } } else { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i+1] = 1; } else //back not match { flag = 0; break; } } else { flag = 0; break; } } } else //single { if(i > 0 && !vis[i-1]) { S = st[i-1]+S; for(j=0;j<100;j++) { if(ss[j] == S) break; } if(j != 100) //pre match { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i] = 0; } else //back not match vis[i] = 1; } } else //pre not match { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i] = 0; } else //back not match { vis[i] = 1; } } else { vis[i] = 1; } } } else { if(i < len-1) { string ks = ""; ks += st[i]; ks += st[i+1]; for(k=0;k<100;k++) { if(ss[k] == ks) break; } if(k != 100) //back match { vis[i] = 0; } else //back not match { vis[i] = 1; } } else { vis[i] = 1; } } } } if(flag) puts("YES"); else puts("NO"); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。