bzoj 4606: [Apio2008]DNA【dp】

写题五分钟读题两小时系列……

看懂题的话不算难，然而我去看了大佬的blog才看懂题……

题目大意是：一个原字符串，其中有一种通配符，合法串的定义是这个串（不含通配符））可以匹配原串并且这个串最多分成k段就能使每一段字典序单调不降。求在所有合法串中字典序第r大的。

设f[i][j][k]表示第i个字符选j，至少需要分成k段的方案数，倒着dp，特判一下通配符，比较基础懒就不多说了

然后对于每个f[i][j]，把k维变成前缀和的形式，因为能分为k段就能分为k+1段。（这里其实当i<k的时候是不对的，但是我写的时候没有特判也过了就没改= =）

然后正着算答案，有点像splay上求k大数的感觉，就是一边匹配一边把r减去当前方案之前（字典序小于当前方案）的方案数。

#include<iostream>

#include<cstdio>

using namespace std;

const int N=50005;

int n,m,a[N],h[305];

long long r,ans,f[N][5][15];

char s[N],b[5];

int main()

{

	h['A']=0,h['C']=1,h['G']=2,h['T']=3,h['N']=4;

	b[0]='A',b[1]='C',b[2]='G',b[3]='T';

	scanf("%d%d%lld%s",&n,&m,&r,s+1);

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

		a[i]=h[s[i]];

	if(a[n]==4)

		f[n][0][1]=1,f[n][1][1]=1,f[n][2][1]=1,f[n][3][1]=1;

	else

		f[n][a[n]][1]=1;

	for(int i=n-1;i>=1;i--)

	{

		if(a[i]==4)

		{

			for(int j=0;j<=3;j++)

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

					for(int l=0;l<=3;l++)

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

		}

		else

		{

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

					for(int l=0;l<=3;l++)

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

		}

	}

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

		for(int j=0;j<=3;j++)

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

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

	for(int i=1,j;i<=n;i++)

	{

		for(j=0;j<=3;j++)

		{

			long long sum;

			if(j<a[i-1])

				sum=f[i][j][m-1];

			else

				sum=f[i][j][m];

			if(r>sum)

				r-=sum;

			else

				break;

		}

		a[i]=j;

		if(a[i]<a[i-1])

			m--;

		printf("%c",b[j]);

	}

	return 0;

}

巴特西

bzoj 4606: [Apio2008]DNA【dp】

最新文章

热门文章