2012-0048

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

Aho组一共n个人(n<=1000)，这n个人要为k次考试出题，考试时间为T1,T2.....Tk(k<=20)每次考试要出p道题（p待求）
最开始每个人有100生命值，第i个人的生命值每秒恢复Ai点，生命值不能为负
每道题分为两部分：idea，data，任意时刻（只要生命值允许）第i个人可以花费Xi点生命完成一个idea或花Yi点生命完成data（idea根data可以由两个人完成，但data不能比idea早出现：给定所有的Ti，Ai，Xi，Yi，求p最大为多少？
对于每次考试分别dp
第l次考试时，先算出每个人的生命值hp[i]，用dp[i][j]表示前i个人出了j个idea时最多出的data数目（注意此处表示时间0到第j次考试的总量，而非为第j次考试出的题）
显然dp[i][j]=max{dp[i-1][j-k]+(hp[i]-k*Ai)/Bi},k是第i人出的idea数
找到最大的x令所有dp[i][x]>=x,则前j次考试每次最多出x/l道题
m次dp以后，x/l的最小值即为答案
不会换行。。。

Aho组一共n个人(n<=1000)，这n个人要为k次考试出题，考试时间为T1,T2.....Tk(k<=20)每次考试要出p道题（p待求）

最开始每个人有100生命值，第i个人的生命值每秒恢复Ai点，生命值不能为负

每道题分为两部分：idea，data，任意时刻（只要生命值允许）第i个人可以花费Xi点生命完成一个idea或花Yi点生命完成data（idea根data可以由两个人完成，但data不能比idea早出现：给定所有的Ti，Ai，Xi，Yi，求p最大为多少？

对于每次考试分别dp

第l次考试时，先算出每个人的生命值hp[i]，用dp[i][j]表示前i个人出了j个idea时最多出的data数目（注意此处表示时间0到第j次考试的总量，而非为第j次考试出的题）

显然dp[i][j]=max{dp[i-1][j-k]+(hp[i]-k*Ai)/Bi},k是第i人出的idea数

找到最大的x令所有dp[i][x]>=x,则前j次考试每次最多出x/l道题

m次dp以后，x/l的最小值即为答案

不会换行。。。