夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色

标签:dp

22 篇文章

Luogu P1896 [SCOI2005]互不侵犯 题解
Describe 题目链接 在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。 注:数据有加强(2018/4/25) 1 <=N <=9, 0 <= K <= N * N Solution 状压DP。 判断两个国王是否相互干扰…
Luogu P3174 [HAOI2009]毛毛虫 题解
Describe 题目链接 对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。例如下图左边的树(图 $1$)抽出一部分就变成了右边的一个毛毛虫了(图 $2$)。 Solution 毛毛虫🐛 很明显,我们可以先预处理出每个点的入度。 显然最后的答案就是$\sum{a_i}-(s-1…
2019.10.6 CSP-S模拟赛T1
前言 考完以后感觉炸了,结果还好(大雾,竟然没有垫底 5+80+20=105(21/52) 题意 对于任意的$1\leq k \leq N$,求有多少个恰好有$k$个叶子节点的二叉树,满足每个节点要么没有子节点,要么有两个子节点,同时不存在一个叶子节点,使得根到它的路径上有不少于$M$条向左的边。 答案对$998244353$取模。 思路 此题发下…
2019.9.15 CSP-S模拟赛
前言 一大波原题来袭!!!(大雾 考得不太好吧0+100+0=100(T3数据出锅了 T1-P5424 [USACO19OPEN]Snakes 题意 有$n$组蛇,每一组蛇有$a_i$条蛇,你有一张网,需要将蛇全部抓住。一次抓一组蛇,因此每次要使网比当前组的蛇的数量大。你可以改变$k$次网的大小,问抓住所有蛇的总浪费空间的最小值? 对于$100 \…
Luogu P3515 [POI2011]Lightning Conductor 题解
题意 题目传送门 已知一个长度为$n$的序列$a_1,a_2,...,a_n$。 对于每个$1\leq i\leq n$,找到最小的非负整数$p$满足 对于任意的$j$,$ a_j \leq a_i + p - \sqrt{| i-j | }$ 思路 首先先把题目中的式子化简一下: $p\geq a_j+\sqrt{|i-j|}-a_i$ 原来就是…
三校集训Part2 NBCX Day7 timegate 题解
题意 原题链接 订正链接 构造一个图,图的所有边权等于$1$,求使$1$到$n$的最短路距离为$k$的方案数。 对于$ 100\text{%}$的数据$n,k \leq 100$ 思路 (为了图(wo)方(tai)便(cai),下文的$m$代表上文题意中的$k$,下文的$k$详见下文) 考虑$dp$。 因为这张图的最短路距离为$k$,所以考虑分层图…
10188. 「一本通 5.6 练习 1」玩具装箱
Link 题意 你可以将一段连续的玩具扔到同一个容器中,如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中,则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 $x$,其制作费用为 $(X-L)^2$,其中 $L…
10152. 「一本通 5.1 练习 3」矩阵取数游戏
题意 帅帅经常和同学玩一个矩阵取数游戏: 对于给定的 $n\times m$ 的矩阵,矩阵中每个元素 $a_{ij}$ 均为非负整数。游戏规则如下: 1. 每次取数时必须从每行各取走一个元素,共 $n$ 个,$m$ 次取完所有元素。 2. 每次取走的各个元素只能是该元素所在行行首或行尾。 3. 每次取数都有一个的分值,为每行取数得分之和,每行取数得…
NOIP2019模拟赛(五)03.31 解题报告
Link NOIP2019模拟赛(五)03.31 A. 「NOIP模拟赛」电阻 题意 询问要得出一个电阻值为$\frac{a}{b}$的元件至少需要多少个电阻值为$1$的电阻。 元件由$3$种方式组成: 一个电阻 一个元件与一个电阻串联 一个元件与一个电阻并联 思路 并联电阻阻值计算 总电阻值为:$总R_总=\frac{1}{\frac{1}{R_…
10166. 「一本通 5.3 练习 1」数字游戏
题意 给定多组数据,每组数据给定三个数:$a,b,n$表示求在区间$[a,b]$内各位数之和模$n=0$的数的个数。 思路 这是一道数位$DP$的模板题。 设$f[i][S]$表示处理到第$i$位,$S$为和。 $f[i][S]=f[i-1][(S+i)%N](0<=k<=Dim[i] or 9)$ 其中$k$的取值范围根据上一位的状态…