Решение задачи Мутация с Codeforces

Без пояснения   Просмотров: 278


Ученые планеты Олимпия проводят очередной эксперимент в области мутации примитивных организмов. Геном организма с этой планеты может быть представлен в виде строки из первых K заглавных букв английского алфавита.

Код

#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k,t,a[33][33],p[33],i,j,ans,x,use;
long long q[1<<22];
char c[210000];
int main(){
	scanf("%d%d%d%s",&n,&k,&t,c+1);
	for(i=0;i<=k;++i)
		for(j=1;j<=k;++j)scanf("%d",&a[i][j]);
	memset(p,-1,sizeof(p));
	for(i=1;i<=n;++i){
		x=c[i]-64;
		for(j=1;j<=k;++j){
			if(p[j]>=0){
				q[p[j]]+=a[j][x];
				q[p[j]|(1<<j-1)]-=a[j][x];
				q[p[j]|(1<<x-1)]-=a[j][x];
				q[p[j]|(1<<j-1)|(1<<x-1)]+=a[j][x];
			}
			p[j]|=1<<x-1;
		}
		p[x]=0;
		use|=1<<x-1;
	}
	for(i=0;i<k;++i)q[1<<i]+=a[0][i+1];
	for(i=0;i<k;++i)
		for(j=0;j<1<<k;++j)if(j>>i &1)q[j]+=q[j^1<<i];
	for(i=0;i<1<<k;++i)if((i&use)==i && q[i]<=t && i!=use)
		ans++;
	printf("%d\n",ans);
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться