rprp

动态规划

图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

全部文章 / 动态规划（共12篇）

UVA10328 Coin Toss

考虑把答案拆成至多有\(n\)张朝上减去至少有\(k-1\)张朝上。显然第一部分的答案就是\(2^n\)，考虑\(DP\)第二部分。设\(dp[i][0/1]\)表示第\(i\)张是反面/正面的情况数。然后有： \[dp[i][0]=dp[i-1][0]+dp[i-1][1] \] ...

动态规划妙啊

2020-05-15

0 422

Luogu P4127 [AHOI2009]同类分布

数位DP 这题最妙的一点在于，由于我们无法存下原来的这个数，我们就考虑存取模之后的值，而这个模数就选择一个可能是最后的每一位数字的和的值。而这个总数只有\(9*18=162\)种，然后存下每一位的和以及从高位到低位的取模结果，数位DP即可。 #include <cstdio> #inc...

数位DP

2020-05-03

0 342