dass90

分类

题解(20)

/ 注册

全部文章（共19篇）

[Algorithm Elementary]买彩票

Thinking Process 总方案数是4n4^n4n，可行的方案的要求是中奖金额≥3∗n\ge3* n≥3∗n，最后做一个约分即可。状态方程 DEFINATION f[i][j]:买了i张彩票赚了j元的方案数 f[0][0] = 1 EQUATION f[i][j] += f[i - 1]...

C

2022-12-27

0 291

[Algorithm Elementary]传球游戏dp

Thinking Process 两种传球方式，一个向左边一个向右边。先不考虑环的情况，直接看链。 Assumption：以第二个人为例子。他只能从第一个人和第三个人手里拿到球。Likewise, it's the same when it comes to i-th person. 状态方程 DE...

C

2022-12-27

0 417

[Algorithm Elementary]迷雾森林

Thinking Process 初始点是(m,1)，终点是(1,n)。终点的最后一个状态只能从(1,n-1)或者(2,n)这两个坐标得来。对(i,j)这个坐标来说，由于题目只允许向上或者是向下走，所以f[i][j]=f[i][j-1]+f[i+1][j]。状态方程自然得到。 NOTICE 此题不...

C C++

2022-12-26

0 448

[Algorithm Elementary]简单的背包dp

Thinking Process 1、先确定状态 f[i][j]:前i个物体能不能装满体积为j的背包? 则现在有两个选择：选第i个物体：要看一下f[i-1][j-c[i]]，它能装下，那这个决定就可以装下不选第i个物体：要看一下f[i-1][j] 故推出状态方程： f[i][j] = f[i...

C C++

2022-12-26

5 383

[Algorithm Elementrary]过河卒

processing 直接考虑最后一步：(i,j)这个位置只能从(i-1, j)和(i, j - 1)这两个位置来，所以定义状态f[i][j]:从A点到(i,j)坐标的路径条数，则推出状态转移方程：f[i][j] = f[i-1][j] + f[i][j-1] NOTICE points (x...

C C++

2022-12-21

0 383

[Algorithm Elementary]Running Median

Thinking Process 一道动态中位数的题。用一个大根堆的优先队列存一半较小值，用一个小根堆的优先队列存一半较大值。如果x小于小根堆的堆顶，则意味着它应该在大根堆中否则，则意味着它应该在小根堆中最后一步，判断两个优先队列的大小是否相差1，如果正好相差1，哪个优先队列大，就输出哪...

C++ C

2022-12-05

0 324

[Algorithm Elementrary]合并果子

Thinking Process 这题很简单。举个例子就能知道思路。三个果子重量分别为10、5、7.合并两次，由于第二次合并出来的值一定是10+5+7=22所以只要第一次合并出来的值小就可以了，即我们取三者之中的最小值5和7。根据这个思路就可以做出这道题。需要注意的是每一次的合并值都得纳入考虑!!...

C C++

2022-12-05

0 372

[Algorithm Elementrary] 栈和排序

Thinking Process We ensure that current stack top is less or equal than the max value from current index to end.So what we need do is to create a list...

C

2022-11-21

0 406

[Algorithm Elementary][NOIP2012]借教室

Thinking Process Use binary search and testify every value. Assume you have known answer and check answer wheather right. If not right, how to update ...

C

2022-11-21

0 294

算法入门【FBI树】

Thinking Process what a easy excersize! but i waste much time on input. DAMN IT! Overall, judge the length of S first. if length == 1, output it direc...

C

2022-10-24

0 458