[APIO2008]DNA

DP

题面

戳我

解析

我们要求出第$r$种方案，莫过于看其前面什么时候有$r-1$种方案。
于是，我们要求出每种情况的方案数。
设$dp[s][m][n]$表示第$i-n$个字母中，已分$m$段，第$i$个字母为s（$s\in\{A,C,G,T\}$)字母的序号 的方案数。
状态转移方程易得：(其中$las$是下一个字母）
$dp[j][k][i]+=dp[l][k-(j>las)][i+1]$
为了下面运算方便，要对$dp[s][m][n]$求前缀和$sum[s][m][n]=\sum_{i=1}^s dp[i][m][n]$
然后就可以从前往后推了，若碰到的字母已知，看是否影响段数就可以了；
如果碰到的字母未知，枚举$s=1...4$的情况，如$r>dp[s][m][n]$，说明第$r$个还在当前枚举字母情况的后面，继续枚举；否则，这一位就应该填当前枚举到的字母。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
char s[N];
int m,k,a[N];
ll r,n,dp[5][15][N],sum[5][15][N];
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
int main()
{
  n=gi();m=gi();r=gi();
  scanf("%s",s+1);
  fp(i,1,n)
    if(s[i]=='A') a[i]=1;else if(s[i]=='C') a[i]=2;else if(s[i]=='G') a[i]=3;else if(s[i]=='T') a[i]=4;
  if(a[n]) dp[a[n]][1][n]=1;
  else fp(i,1,4) dp[i][1][n]=1;
  fq(i,n-1,1)
    fp(j,1,4)
    if(!a[i]||a[i]==j)
      fp(k,1,m)
    fp(l,1,4)
    dp[j][k][i]+=dp[l][k-(j>l)][i+1];
  fp(i,1,4)
    fp(j,1,n)
    fp(k,1,m)
    sum[i][k][j]=sum[i][k-1][j]+dp[i][k][j];
  re int las=0;
  fp(i,1,n)
    if(a[i])
      {
    if(a[i]<las) --m;
    las=a[i];
    putchar(s[i]);
      }
    else
      {
    re int j;
    for(j=1;j<=4&&r>sum[j][m-(j<las)][i];j++) r-=sum[j][m-(j<las)][i];
    if(j==1) putchar('A');if(j==2) putchar('C');if(j==3) putchar('G');if(j==4) putchar('T');
    if(j<las) --m;
    las=j;
      }
  puts("");
  return 0;
}