wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共8篇）

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

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

动态规划

2020-06-17

1 983

【每日一题】最大子矩阵

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

【题解】牛客练习赛64

A 怪盗-1412 problem 用个，个，个进行排列，求最多有多少个子序列。 solution 显然让所有的4和2分别相邻答案会更大。然后就是将1分成两份，分别放在4两边。如果前面的有个，那么答案就是，这是一个二次函数，当时取得最大值。 code /* * @Author: wxyww * @D...

字符串贪心动态规划

2020-05-24

2 724

【题解】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

【题解】牛客练习赛61

迟到1h，险些掉分，呼~ A 数据范围很小，模拟签到题。 /* * @Author: wxyww * @Date: 2020-04-10 19:52:33 * @Last Modified time: 2020-04-10 20:02:50 */ #include<cstdio> #in...

搜索动态规划点分治

2020-04-11

1 609