题目跳转

HDOJ-1560

题目大意

给你若干小段DNA序列（字符串），请你找到一个DNA序列（字符串），使得这些小段DNA序列（字符串）都能被这个字符串的子序列（非字串，子序列可不连续）匹配。

输出最小长度。

思路

IDA*

容易分析出，数据庞大，而正解大概率在比较小的层数，便选取IDA*

剪枝

1. 从当前字串的最大长度开始。
2. 若某一字串未匹配的长度比剩余层数大，则无解。

反思

拿到题目，犹豫怎么搜，果然还是不够暴力。。

手动加O2是因为昨日CF，本地与OJ输出不同的惨痛教训。OnO

CODE

#pragma GCC optimize(2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

typedef long long LL;

int n, depth;
int len[12], idx[12];
char DNA[5] = "ACGT";
char s[12][50];

bool dfs(int u)
{
  if (u == depth)
  {
    for (int i = 1; i <= n; i++)
      if (len[i] != idx[i])
        return false;
    // cout << s[0] << endl;
    return true;
  }
  for (int i = 1; i <= n; i++)
    if (len[i] - idx[i] > depth - u)
      return false;
  // cout << s[0] << endl;
  // for (int i = 1; i <= n; i++)
  //   cout << idx[i] << ' ' << len[i] << endl;
  // cout << endl;
  for (int i = 0; i < 4; i++)
  {
    int rec[12], rec_idx = 0; // 为局部变量，变成全局，导致数据混乱
    s[0][len[0]++] = DNA[i];
    for (int j = 1; j <= n; j++)
    {
      if (idx[j] < len[j] && s[j][idx[j]] == s[0][len[0] - 1])
      {
        rec[rec_idx++] = j;
        idx[j]++;
      }
    }
    if (dfs(u + 1))
      return true;
    for (int j = 0; j < rec_idx; j++)
      idx[rec[j]]--;
    len[0]--;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  int T;
  cin >> T;
  while (T--)
  {
    depth = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
      cin >> s[i];
      len[i] = strlen(s[i]);
      depth = max(depth, len[i]);
    }
    // 回来一遍缺少初始化，且在里面不需要，因为dfs会还原
    memset(idx, 0, sizeof idx);
    s[0][0] = '\0';
    len[0] = 0;
    while (!dfs(0))
      depth++;

    cout << depth << endl;
  }
  return 0;
}