[APIO2008]DNA 题解

首先呢，看到 A C G T 对应不同的权值，第一步就是把字母转换成数字。

我们分别对 A->1 C->2 G->3 T->4 进行标号，之后方便 \(\text{dp}\) 。

然后看到题目中对于一个范式的定义：

一个DNA序列属于范式 \(-j(j>1)\) ，只要它属于范式 \(-(j-1)\) 或者是一个范式 \(-(j-1)\) 和一个范式 \(-1\) 的连接。

那我看了半天才看懂是什么意思，简洁来说就是范式为 \(j\) 的串同时也是范式为 \(j+1\) 的串。

其实讲到现在也就是表达一个前缀和的关系。

那我们显然要把前缀和拆开，这样的话更利于我们 \(\text{dp}\) 转移。

用符合题目的思路来说就是：隔断 \(j\) 到 \(j+1\) 这两个范式之间的直升关系。

最后再做一遍前缀和恢复就好了。

考虑怎么 \(\text{dp}\) 。

我们设 \(f_{i,j,k}\) 表示到了第 \(i\) 个位置，当前位是 \(k\) ，且范式为 \(j\) 的方案数。

那么可以得到

\[f_{i,j,k} = \sum_{type = 1}^4f_{i+1,j-[k > type],type}
\]

这个也很好理解吧。

就是说我从后向前转移，枚举后一位的优先级 \(type\) 。

如果当前的优先级 \(k\) 大于后一位的优先级 \(type\) 那么范式一定加一。

这也就是为什么转移方程中会出现 \(j-[k > type]\) 。

转移完成后要记得做一次前缀和。

具体细节可以看代码。

既然 \(f_{i,j,k}\) 都求出来了，那么输出方案也不难了。

对于 \(r\) 比当前方案数多时，那就增加当前的等级，并更新 \(r\) 。

Code

#include <cstdio>

#include <iostream>

#include <algorithm>

#define file(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

#define quad putchar(' ')

#define Enter putchar('\n')

#define int long long

const int N = 5e4 + 5;

int m, k, r, a[N], f[N][15][5];

char c[N];

inline void print(int num) {

  if (num == 1) putchar('A');

  if (num == 2) putchar('C');

  if (num == 3) putchar('G');

  if (num == 4) putchar('T');

}

signed main(void) {

  // file("P3624");

  std::cin >> m >> k >> r;

  scanf("%s", c + 1);

  for (int i = 1; i <= m; i++) {

    if (c[i] == 'A') a[i] = 1;

    if (c[i] == 'C') a[i] = 2;

    if (c[i] == 'G') a[i] = 3;

    if (c[i] == 'T') a[i] = 4;

  }

  if (a[m] != 0) {

    f[m][1][a[m]] = 1;

  } else {

    for (int i = 1; i <= 4; i++)

      f[m][1][i] = 1;

  }

  for (int i = m - 1; i >= 1; i--) {

    if (a[i] != 0) {

      for (int j = 1; j <= k; j++) {

        for (int l = 1; l <= 4; l++)

          f[i][j][a[i]] += f[i + 1][j - (a[i] > l)][l];

      }

    } else {

      for (int num = 1; num <= 4; num ++) {

        for (int j = 1; j <= k; j++) {

          for (int l = 1; l <= 4; l++)

            f[i][j][num] += f[i + 1][j - (num > l)][l];

        }

      }

    }

  }

  for (int i = 1; i <= m; i++)

    for (int j = 1; j <= k; j++)

      for (int l = 1; l <= 4; l++)

        f[i][j][l] += f[i][j - 1][l];

  int last = 0;

  for (int i = 1; i <= m; i++) {

    if (a[i] != 0) {

      print(a[i]);

      if (a[i] < last) k --;

      last = a[i];

    } else {

      int chose;

      for (chose = 1; chose <= 4 && r > f[i][k - (chose < last)][chose]; chose ++)

        r -= f[i][k - (chose < last)][chose];

      print(chose);

      if (chose < last) k --;

      last = chose;

    }

  }

  std::cout << std::endl;

  return 0;

}

巴特西

[APIO2008]DNA 题解

Code

最新文章

热门文章