Camouflagetch

分类

题解(4)

/ 注册

全部文章（共4篇）

[NOIP1999]拦截导弹

题目链接改题目分为两个问题第一个就是求最长的不上升子序列的长度第二个是求原序列最少可划分为多少不上升子序列第二个问题根据dilworth定理，求可划分的最少的不上升子序列等于求最长的上升子序列的长度。所以该题的本质上就是求一个最长的上升子序列和一个最长的不上升子序列。而对于求一个单调上升子序...

C++ 贪心动态规划

2022-05-02

0 363

[NOI1998]免费馅饼

题目链接对于输入的每行四个数据，由于题目中说到了“当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼”，所以我们首先将从h到1消耗的时间不是v的整数倍的选项通过continue过滤掉。将那些符合题目条件的数，将其能产生的价值保存到二维数组q中，第一维表示水平位置，第二维表示时间，...

动态规划

2022-04-28

6 514

NC17508 指纹锁

set中重载运算符()进行自定义排序 ">using namespace std; int m, k, x; struct cmp{ bool operator()(const int &a, const int &b) const{ if(abs(a - b...

C++ 模拟

2022-04-16

0 396

[JSOI2007]建筑抢修

这道题首先通过排序让截止时间早的尽可能排在前面，然后通过优先队列(降序)q保存抢修的建筑所花费的时间，然后对结构体数组进行遍历，如果现在花费的总时间加上抢修现在这个建筑所需要的时间之和小于等于本建筑的截止时间，那么便对他进行抢修，更新q、t。如果现在花费的总时间加上抢修现在这个建筑所需要的时间之和大...

C++ 堆(优先队列) 贪心

2022-04-15

0 255