首页 > 其他分享 >cf1606e-solution

cf1606e-solution

时间:2024-02-28 13:58:00浏览次数:27  
标签:最大值 solution 血量 cf1606e binom dp

CF1606E Solution

link

考虑 dp。

注意到这个题造成的伤害与剩余人数有关,每次消灭的人数又与剩余人的血量最大值有关:

设 \(dp_{i,j}\) 表示剩下 \(i\) 个人中血量最大值为 \(j\) 的方案数。

显然当 \(i-1>=j\) 时一次伤害就可以杀光所有人,于是这时 \(dp_{i,j}=j^i-(j-1)^i\)(只需让最大血量为 \(j\))。

当 \(i-1<j\) 时,一次伤害会杀掉一部分人,我们考虑枚举剩下的人数 \(k\),则此时

\[dp_{i,j}=\sum_{k=2}^idp_{k,j-i+1}\binom i k(i-1)^{i-k} \]

其中乘上 \(\binom i k\) 表示从 \(i\) 个人中选出 \(k\) 个留下来,乘上 \((i-1)^{i-k}\) 表示死去的人血量值可以在 \([1,i-1]\) 中任取。

\(\mathcal O(n^2m)\) 直接计算即可。

标签:最大值,solution,血量,cf1606e,binom,dp
From: https://www.cnblogs.com/iorit/p/18040127

相关文章

  • cf1599j-solution
    CF1599JSolutionlink题意:给你一个长为\(n\)的序列\(b\),请你构造一个长为\(n\)的序列\(a\),满足\(b\)中的数都能由\(a\)中两个不同下标的数相加得到。无解报告NO,\(n\le10^3,b_i\le10^6\)。我们发现如果我们能用\(a_1\sima_m\)来凑出\(b_1\simb_m\),剩下的令......
  • cf1583h-solution
    CF1583HSolutionlink第一问容易处理,将边权从大到小排序,并查集维护一下连通块最大值简单搞搞就好。考虑第二问。我们对原树,按照\(t\)的权值建造克鲁斯卡尔重构树,那么两点的lca权值即它们路径上边权最大值。同样按照边权\(c\)从大到小将边排序,维护连通块内最大值的同时,维......
  • cf1555f-solution
    CF1555FSolutionlink分析一张图中的环,我们可以考虑把图表示为一棵生成树加上许多非树边。对于这题,我们考虑动态维护一片森林,在每次准备加一条边\((u,v)\)时:如果这条边加进去后与森林不形成环,那么它与图肯定也不形成环,那么直接加进森林中。如果这条边是森林的一条非树......
  • cf1553f-solution
    CF1553FSolutionlink首先显然地\(\displaystylep_i=p_{i-1}+\sum_{j=1}^{i-1}a_j\bmoda_i+\sum_{j=1}^{i-1}a_i\bmoda_j\)。那么两部分分开来算。\(\displaystyle\sum_{j=1}^{i-1}a_j\bmoda_i\):我们知道\(x\bmody=x-y\lfloor\fracxy\rfloor\),那么我们先把答案加上......
  • cf1548c-solution
    CF1548CSolutionlink题意说人话就是每次给\(x\)求\(\displaystyle\sum_{i=1}^n\binom{3i}x\)。由于多组询问,考虑能不能生成函数。设\[\begin{aligned}f_k&=\sum_{i=1}^n\binom{3i}k\\F(x)&=\sum_{i=0}^\inftyf_{i}x^i\\&=\sum_{i=0}^\infty\sum_{j=1}^n\bin......
  • cf1491h-solution
    CF1491HSolutionlink考虑分块。按照点的编号分块,维护\(b_i\)表示\(i\)往上跳遇到的第一个与\(i\)异块的点。对于散块修改,直接暴力重构整块的\(b\)。重构方式是,如果\(a_i\)与\(i\)异块,则\(b_i\getsa_i\);否则\(b_i\getsb_{a_i}\)。对于整块,打标记维护整体减了多......
  • cf1491e-solution
    CF1491ESolutionlink首先,把一棵大小为\(f_i\)的树切成两棵树只能是切成\(f_{i-1}\)和\(f_{i-2}\)的,而且最多只有两种切的方案。证明考虑分类讨论是否有大小为\(f_{i-1}\)的子树(以\(1\)为根)即可,感性理解就好。接下来你可以选择每次暴力通过两种割边方案递归检验,但是......
  • cf1487g-solution
    CF1487GSolutionlink想一想没有字符的限制怎么做。首先,没有长度大于一的奇回文串显然等价于没有长度为\(3\)的回文串。也就等价于\(\foralli\in[1,n-2],s_i\not=s_{i+2}\)。那么在没有限制的情况下,我们确定好了前两位字符,后面的\(n-2\)位各有\(25\)种字符可选。方......
  • cf1446d2-solution
    CF1446D2Solutionlink首先,最终答案区间中的众数一定包括整个序列的众数\(K\)。证明:设这个区间中众数出现次数为\(cnt\)。如果上述不成立,由于\(K\)在这个区间中出现次数小于\(cnt\),我们将区间向两边延申,\(K\)的出现次数应当不断增加直到等于区间的众数出现次数。这样子......
  • cf1396d-solution
    CF1396DSolutionlink题面:给你一个\(L\timesL\)的矩形,有\(n\)个点放在不同的格子内,每个点有颜色,共\(k\)种颜色,求有多少个矩形满足其内部含有所有颜色的点,对\(10^9+7\)取模。\(k\len\le2000,L\le10^9\)。首先离散化。看到数据范围说明可以枚举矩形的某个端点或者......