wxyww

题解

未归档(12) 精品(28)

/ 注册

全部文章 / 题解（共6篇）

【每日一题】小仙女过生日啦

solution 如果给出的是一个凸多边形，那么问题其实就是三角剖分，用不相交的对角线将多边形划分为多个三角形，要求最大的三角形面积最小。求这个面积。用表示从第个点到第个点进行三角剖分的答案。转移就枚举一个满足，表示以这三个点为顶点的三角形的面积，这个可以直接用叉积计算。如果给出的不是凸多...

动态规划

2020-06-17

1 984

【每日一题】最大子矩阵

solution 注意到。考虑时如何做。令表示前i个位置选出了j段的最大价值。转移就是同样的方法我们可以类比出时的做法。令表示第1列选到了第i个数，第二列选到了第j个数，总共选了k个矩阵的最大价值。转移就枚举一下最后放的一个矩阵，如果最后一个矩阵放在了第1列，那就从转移过来。如果最后一个矩...

动态规划

2020-06-05

3 991

【每日一题】管道取珠

solution 我们可以将问题转化为进行两次游戏，最终输出的序列相同的方案数。为什么可以这么转化呢？我们尝试用式子表示这个新问题，对于一种序列，如果在一次游戏中取到他的方案数为，那么根据乘法原理，在两次游戏中都取到他的方案数就是，那么所有可能序列的方案数之和自然就是了。那这个问题怎么做呢？我们...

动态规划

2020-05-28

1 612

【每日一题】货币系统

solution 想起当年noip赛场上没做出来这道降智题就来气。。。这个题目其实讲的也就是去掉最多的元素，使得剩下的元素可以组成原来可以组成全部数字。仔细想一下，其实就是将原数组排序之后，如果比较大的那个可以被比较小的表示出来，那么这个元素我们就可以删去了。所以我们用表示前i个元素是不是可以组...

背包动态规划

2020-05-26

1 559

【题解】NC5531D 牛牛的01限定串

solution 考虑dp。用表示对于t的前个位置，有个位置为1最小得分。显然当前面1的个数确定之后，后面1的个数也确定了。也就是我们可以计算对于位置它的前缀是否和s相似，它的后缀是否和s相似，然后就可以计算出i位置的贡献。枚举i位置是'0'还是'1'转移即可。 code /* * @Author...

动态规划

2020-05-11

2 723

【每日一题】子序列

solution 我们大胆猜测：如果当前已经选择了一些位置，加入新位置时只要与已选的最后一个位置满足题目条件，那么肯定与前面的每个位置都满足条件。下面给出证明。证明:设已有。对于第一个不等式，同时变为，因为底数为正数，所以不等式符号不变。即变为,对于第二个不等式，同时变为，即变为。然后将这两个新...

数学动态规划

2020-04-23

1 710