BZPRO

#4067. [Ctsc2015]gender

内存限制：512 MiB 时间限制：50 Sec
提交 提交记录 讨论

题目描述

 21世纪是生命科学的世纪。人类投入了大量人力物力研究生命科学，旨在对各类生物的生存机理产生更加深入的理解，

以更好地了解人类自身，提高生活质量。Q国政府首先在绵羊中开展了性别改造研究，希望通过基因重组改变性别的方式
增强整个绵羊种群的生存能力。若此计划能够顺利研究成功，人类将掌握随意改变动物性别的黑科技，这将是生命科学
研究史上一个重要的里程碑。 
Q国政府从绵羊群中挑出M只绵羊作为实验样本，这M只绵羊中存在K条长度为N的单一性别的血缘链。所谓“血缘链”
是指的一条由父（母）子（女）关系组成的链，比如爷爷-爸爸-儿子就是一条血缘链。“单一性别”的意思是每条血缘链
中所有个体的性别均一致，同为雄性或同为雌性。血缘链长度指的是一条血缘链中个体的数量，比如爷爷-爸爸-儿子是一
条长度为3的血缘链。这K条血缘链并不相交。 
注意并不是每只绵羊都必须属于一条血缘链，有些绵羊可能不属于任何血缘链，因此N*K<=M。除去血缘链外，同辈绵羊还
会有“繁衍关系”的存在。两只异性绵羊如果曾经繁殖过后代，那么它们之间就会产生“繁衍关系”。注意繁衍关系只会
出现在同辈异性绵羊个体之间，这里“同辈”表示两只绵羊的辈份相同，即绵羊只会与它的兄弟姐妹辈产生“繁衍关系”，
而不会与父母或子女或其他更远的辈份之间产生“繁衍关系”。 
对绵羊进行性别修改需要花费巨大的实验开销，修改绵羊i的性别需要花费ci的修改代价。除此以外，修改绵羊性别还会对
繁衍关系的稳定度产生影响：每对繁衍关系j有初始稳定度bj和衰减系数dj，当所有的性别修改操作完成后，若双方性别均
未改变，则此关系稳定度sj=bj，若双方性别互换，则稳定度sj=floor(bjdj)，其他情况下稳定度sj=0。 
给定每只绵羊的性别、性别修改代价、所有血缘链关系很繁衍关系，Q国政府希望你来设计一套性别搞糟方案，使总收益最大。
收益计算方式如下： 
 
其中A为改造后血缘链相邻两者为异性的情况数量，S为改造后繁衍关系稳定度之和，即S=∑jsj，C为修改绵羊性别带来的代价
之和，即C=∑ici。 

输入格式

 第一行包含四个非负整数N,K,M,P，分别为血缘链的长度，血缘链的数量，实验样本中的总绵羊数和繁衍关系的数量。 

第二行为一个M个字符的字符串，每个字符为'M'或'F'，描述了这M只绵羊的初始性别。'M'表示雄性，'F'表示雌性。 
第三行M个正整数ci，表示修改每只绵羊性别的代价。 
下面K行每行N个整数，分别描述这K个血缘链中绵羊编号（所有绵羊用1到M的整数编号），保证每条链中的绵羊均为同性，
且链互补交叠。 
下面P行每行三个整数x,y,b和一个实属d，表示绵羊x与绵羊y存在繁衍关系，且初始关系稳定度为b，衰减系数为d。
保证x与y的初始性别不同，x和y为同辈，同一条关系只会在数据中描述一次。 

输出格式

仅包含一行一个整数，表示改造计划的最大收益。 

样例

样例输入


			
3 2 6 2

MMMFFF

10000 200 10 10000 200 10

1 2 3 

4 5 6 

2 5 20 0.1

3 6 20 0.9

样例输出


			
360

数据范围与提示

 样例解释1： 


改性别为MMFFFM。收益为。 

A=2是因为血缘链1-2-3中2与3性别的不同，血缘链4-5-6中5与6的性别不同。 



数据范围 

对于10%的数据，满足M<=20； 

对于10%的数据，满足dj=0； 

对于10%的数据，满足dj=0.5； 

上述三类数据两两没有交集。 

对于100%的数据，N<=50，K<=4，M<=1000，P<=10000，0.0<=dj<=1.0，bj和ci均不大于10000，dj的小数位数不超过6。 

BZPRO Powered by Remmina.
Github Repository