Link 题意 你可以将一段连续的玩具扔到同一个容器中，如果要将 $i$ 号玩具到 $j$ 号玩具 $(i\le j)$ 放到同一个容器中，则容器长度不小于 $x=j-i+ \displaystyle\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(X-L)^2$，其中 $L…

题意 帅帅经常和同学玩一个矩阵取数游戏： 对于给定的 $n\times m$ 的矩阵，矩阵中每个元素 $a_{ij}$ 均为非负整数。游戏规则如下： 1. 每次取数时必须从每行各取走一个元素，共 $n$ 个，$m$ 次取完所有元素。 2. 每次取走的各个元素只能是该元素所在行行首或行尾。 3. 每次取数都有一个的分值，为每行取数得分之和，每行取数得…

题意 某城市的街道呈网格状，左下角坐标为 $A(0, 0)$，右上角坐标为 $B(n, m)$，其中 $n \ge m$。现在从 $A(0, 0)$ 点出发，只能沿着街道向正右方或者正上方行走，且不能经过图示中直线左上方的点，即任何途径的点 $(x, y)$ 都要满足 $x\ge y$，请问在这些前提下，到达 $B(n, m)$ 有多少种走法。 思…

题意 给定多组数据，每组数据给定三个数：$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$的取值范围根据上一位的状态…

题意 高二数学《绿色通道》总共有 $n$ 道题目要抄，编号 $1\dots n$，抄第 $i$ 题要花 $a_i$ 分钟。小 Y 决定只用不超过 $t$ 分钟抄这个，因此必然有空着的题。每道题要么不写，要么抄完，不能写一半。下标连续的一些空题称为一个空题段，它的长度就是所包含的题目数。这样应付自然会引起马老师的愤怒，最长的空题段越长，马老师越生气。…

题意 有一个 $a\times b$ 的整数组成的矩阵，现请你从中找出一个 $n\times n$ 的正方形区域，使得该区域所有数中的最大值和最小值的差最小。 思路 设$dp[i][j][k]$表示以$i,j$为左上角的正方形变成为$k$内的最大值，$dp2[i][j][k]$表示最小值。 可知，$dp[i][j][k]=max(dp[i+1][j…

三倍经验 LOJ #2240. 「CQOI2014」数三角形 BZOJ 3505: [Cqoi2014]数三角形 Luogu P3166 [CQOI2014]数三角形 （Luogu要大一些。。。） 题意 给定一个$n \times m$的网格，请计算三点都在格点上的三角形共有多少个。下图为$4 \times 4$的网格上的一个三角形。注意三角形的三…

题意 跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有三颗棋子，分别在 $a,b,c$ 这三个位置。我们要通过最少的跳动把他们的位置移动成 $x,y,z$（注意：棋子是没有区别的）。跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过一颗棋子。…

题意 小S养了$M$只猫，雇了$P$位饲养员。农场旁边有$N$座山，从$1$到$N$编号，第$i$座山与第$i-1$座山的距离为$D_i$，饲养员都住在$1$号山上。 有一天，第$i$只猫到第$H_i$座山玩，一直玩到$T_i$停止。饲养员们必须接回所有的猫，饲养员们行走的速度为$1$个单位每单位时间。 问如何计划每个饲养员从$1$号山出发的时间，…

题意 有$n$个骑士，每个骑士有一个自己的战斗值，每个骑士也有且仅有唯一一个自己讨厌的骑士，每个骑士不可能与自己讨厌的骑士一起上场战斗，问最高的战斗值之和是多少？ 思路 这道题与没有上司的舞会很像。但是注意，这道题可能会有环的存在，所以我们需要对于每个环，把它切割成两部分，再分别树形dp，然后取最大值，加入ans中。 树形dp的思路很简单： 设$f…