yjq_1999

n>21时无解

考虑n<=21的情况，用dp[S]表示利用S里面的字符可以到的最远的位置，预处理nxt[i][j]表示i后面第一个j字符出现的位置进行转移，复杂度O(N*2^N)

代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <memory.h>

using namespace std;

int T,n;

const int MAXN = 1<<21;
int dp[MAXN];
char s[510];
int nxt[510][30];
int main() {
#ifdef YJQ_LOCAL
  freopen(".in","r",stdin);
  freopen(".out","w",stdout);
#endif
  scanf("%d",&T);
  while (T --) {
    scanf("%d%s",&n,s + 1);
    int L = strlen(s + 1),N = (1 << n);
    if (n > 21) {
      puts("NO");
    }
    else {
      memset(dp,0,sizeof dp);
      for (int j = 0;j < n;j ++) nxt[L + 1][j] = L + 1;
      for (int i = L;i ;i --) {
        for (int j = 0;j < n;j ++) nxt[i][j] = nxt[i + 1][j];
        nxt[i][s[i] - 'a'] = i;
      }
      for (int i = 0;i < N;i ++) {
        for (int j = 0;j < n;j ++) {
          if (!((i >> j) & 1)) {
            dp[i ^ (1 << j)] = max(dp[i ^ (1 << j)],nxt[min(L + 1,dp[i] + 1)][j]);
          }
        }
      }
      if (dp[N - 1] > L || dp[N - 1] < 1) puts("NO");
      else puts("YES");
    }
  }
}