P3989 [SHOI2013]阶乘字符串
题目描述
给定一个由前\(n(\le 26)\)个小写字母组成的串\(S(|S|\le 450)\)。串\(S\)是阶乘字符串当且仅当前 \(n\) 个小写字母的全排列(共\(n!\)种)都作为的子序列(可以不连续)出现。
请判断出给定的串是否是阶乘字符串。
当\(n> 21\)时无解,原因不明,留坑
剩下的状压一下就好了
\(dp_s\)表示集合\(s\)的所有排列出现的最前位置
枚举集合最后一个元素更新
\(yuu_{i,j}\)表示\(j\)在\(i\)之后出现的最前位置
Code:
#include#include int T,n,dp[1<<21],yuu[460][26];char s[460];int max(int x,int y){return x>y?x:y;}int main(){ scanf("%d",&T); while(T--) { scanf("%d%s",&n,s+1); if(n>21) { puts("NO"); continue; } int len=strlen(s+1); for(int i=0;i >i&1) dp[s]=max(dp[s],yuu[dp[s^(1<
2019.2.14