和我签订契约，成为马猴烧酒吧！
这题还挺有趣的...
区间dp（没想到吧）
设当前的Witch串为s
f[x][i][j]代表字符x是否能克制s中的区间(i,j)
在dp的过程中，因为x只有'A'-'Z'26种，所以这里就直接暴力枚举。
而x的克制或孵化规则，一共也只有20种，所以也直接枚举。
首先初始化：
克制关系都是1v1的，所以首先要把哪个字符能克制s[i]处理出来。
也就是说，对于x='A'-'Z'，检查x是否能克制s[i]。
至于x能不能在Spell中出现...先不用考虑。
枚举i、x、x的克制关系，若有x->s[i]，则f[x][i][i] = true
for(int i = 0; i < n; i++) for(int x = 0; x < 26; x++) for(int t = 0; t < atk[x].size(); t++) if(atk[x][t] == s[i]) f[x][i][i] = 1; // atk[x][t]=y 则x的第t个克制关系为 x->y
最开始只有一个S，所以想消灭整个Witch，必须要孵化新的。
一张卡只能孵化成两张，所以枚举断点k，
设a,b代表字符x的某个孵化关系所孵化出的第1,2张卡的字符
(i,k)由a克制，(k+1,j)由b克制，
状态转移方程：f[x][i][j] = f[a][i][k] && f[b][k+1][j]
for(int len = 2; len <= n; len++) for(int i = 0; i+len-1 < n; i++) { int j = i+len-1; for(int x = 0; x < 26; x++) for(int t = 0; t < spl[1][x].size(); t++) for(int k = i; k <= j; k++) if(f[spl[1][x][t]-'A'][i][k] && f[spl[2][x][t]-'A'][k+1][j]) f[x][i][j] = 1; } // spl[1][x][t]=y,spl[2][x][t]=z 则x的第t个孵化关系为x->yz
最后检查f['S'][1][len]是否为true就可以了！
完整代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq #include<vector> using namespace std; int n,m; int f[30][25][25]; char s[25]; vector <char> atk[30],spl[3][30]; int main() { scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { scanf("%s",s); atk[s[0]-'A'].push_back(s[3]); } for(int i = 1; i <= m; i++) { scanf("%s",s); spl[1][s[0]-'A'].push_back(s[3]); spl[2][s[0]-'A'].push_back(s[4]); } while(~scanf("%s",s)) { n = strlen(s); memset(f,0,sizeof(f)); for(int i = 0; i < n; i++) for(int x = 0; x < 26; x++) for(int t = 0; t < atk[x].size(); t++) if(atk[x][t] == s[i]) f[x][i][i] = 1; for(int len = 2; len <= n; len++) for(int i = 0; i+len-1 < n; i++) { int j = i+len-1; for(int x = 0; x < 26; x++) for(int t = 0; t < spl[1][x].size(); t++) for(int k = i; k <= j; k++) if(f[spl[1][x][t]-'A'][i][k] && f[spl[2][x][t]-'A'][k+1][j]) f[x][i][j] = 1; } if(f['S'-'A'][0][n-1]) printf("YES "); else printf("NO "); } return 0; }