Day24h

分类

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 数据结构(8) 未归档(5) 模板(23)

/ 注册

全部文章（共22篇）

String Compression

F. String Compression 利用dp和前缀数组来写 dp[i] 所表示的东西是字符串 s[0:i] （不包括 s[i]）能够压缩的最短长度 bj[i][j] 表示的是字符串 s[i:j+1] （不包括 s[j+1]）能够压缩的最短长度代码: // Created ...

前缀函数 dp

2019-08-09

0 408

Complete the Projects

F1. Complete the Projects (easy version) F2. Complete the Projects (hard version) 参考：Complete the Projects 简单说就是当 b>=0 是肯定是 a 小的优先的，需要注意的就是 b&l...

贪心 dp

2019-08-14

0 415

打地鼠Ⅱ

打地鼠Ⅱ 这个也是一个 dp ，可能是我 dp 的题写的太少了吧，后面得多练练 dp 的题。思路：把所有的数据存于一个结构体中，然后进行排序，排序的规则是，时间短的优先，分数高的优先。 dp[i]：表示打i个地鼠可以得到的最大分数最后求ans的时候需要在所有的dp[]...

贪心 dp

2019-08-21

0 785

Tiling_easy version

Tiling_easy version 思路：关于dp这种东西，有一点必须要想明白，就是状态与状态之间的转换关系，就比如说要求5个骨牌的方案数，因为有两种骨牌，那么可以用dp[3]+两个横着的骨牌或者一个2*2的骨牌，或者是dp[4]+一个竖着的1*2骨牌来构成，那么递推的公式就是dp[5]...

dp

2019-10-10

0 416

Max Sum Plus Plus

A - Max Sum Plus Plus 参考：HDU 1024 Max Sum Plus Plus（动态规划，给定一个数组，求其分成m个不相交子段和最大值的问题）思路：想了好久好久...才把它想懂。但是还是不明白为什么最初的代码会WA 用dp来写这道题，最原始的公式为d...

dp

2019-10-16

0 475

Monkey and Banana

C - Monkey and Banana 参考：ACM HDU 1069 Monkey and Banana (动态规划）思路：对于这道DP题来说，如果以高度或者说砖块的个数来作为储存的状态的内容，显然是不合适的。不难看出，这道题主要是想求一个最长有序子序列，那么我们首...

dp 最长有序子序列

2019-10-17

0 447

Doing Homework

D - Doing Homework 参考：ACM HDU 1074 Doing Homework(位运算，搜索，状态压缩DP）思路：因为每个作业给定的顺序就是按照字典序的顺序，所以不用再多去比较。该题的n不大，同时我们又想用DP来完成这道题，那么一个很好的办法来储存状态...

状态压缩 dp

2019-10-26

0 385

Super Jumping! Jumping! Jumping!

E - Super Jumping! Jumping! Jumping! 思路：就是按照求最长有序子序列的思路来写，跟Monkey and Banana的思路大同小异。代码： // Created by CAD on 2019/10/26. #include <bits/st...

dp 最长有序子序列

2019-10-26

0 393

免费馅饼

G - 免费馅饼参考：免费馅饼~-~（hdu 1176）思路：刚开始始的时候想dfs，但是数据太多了，而且有些情况也会漏掉。于是DP是最好的选择，但是DP的时候又要考虑到一点，起始位置是固定的，无法确定最大值与起始位置的联系，所以，需要反着来算，从最后一秒开始计算，对...

dp

2019-10-26

0 316

Tickets

H - Tickets 参考：Tickets——H 思路：对于每一个买票的人来说，只需要决定他是自己买票还是跟前面的人一块买票即可。假设三个人 A B C，当 C 要跟 B 一块买票的时候，B 不能够跟 A 一起买。那么状态方程就应该是dp[i]=min(dp[i-1...

dp

2019-10-26

0 386