Day24h

分类

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

/ 注册

全部文章（共131篇）

不要62

不要62 参考： HDU2089 不要62 标准数位DP 从最高位开始递归，如果有4或者62则不往下走。 dp[i][j]表示的是有i位数字，且第i位数字为j并满足题给条件的数字的个数其实也就是记忆化搜索的感觉，保留搜过的状态，以避免重复运算。代码： //...

数位DP dp

2019-11-09

0 416

windy数

windy数参考：题解 P2657 【[SCOI2009]windy数 windy数数位dp练习题——只要学了数位dp就异常简单的题用数位dp解决这个问题。数位 DP 问题往往都是这样的题型，给定一个闭区间[l,r]，让你求这个区间中满足某种条件的数的总...

数位DP dp

2019-11-09

0 392

Equalizing Two Strings

F. Equalizing Two Strings 有几种情况可以直接判定结果： ① 字母对应个数不一样，可直接判NO ② 当不满足①时，如果有一个字母有2个及以上的个数，也可直接判YES ③ 当不满足①②时我们可以知道，此时的字符串最多也只有26个字符，所以可以直接暴力，一个字符串...

字符串暴力

2019-11-07

0 529

Yet Another Division Into Teams

E. Yet Another Division Into Teams 首先要想明白一个东西，就是当一个小组达到六个人的时候，它一定可以拆分成两个更优的小组。这个题可以用动态规划来写，用一个数组来保存状态，用一个队列来尝试新的状态，但是因为上面的这个特性，每一次只会有三个新的状态。 ...

dp

2019-11-07

0 453

Common Subsequence

L - Common Subsequence 参考：ACM POJ 1458 Common Subsequence (最长公共子序列，动态规划）思路：二维动态规划。 dp[i][j]：在截止至s1的i-1，s2的j-1位置，两个串的最长公共子序列长度。动态规划方程： ...

最长公共子序列 dp

2019-11-05

0 355

Shichikuji and Power Grid

D. Shichikuji and Power Grid 参考：Codeforces Round #597 (Div. 2) 思路：一个很裸的最小生成树。把建立基站看成是，城市与源点（虚构的）建边。由此建立最小生成树，即可得出答案。代码： // Created by C...

最小生成树

2019-11-02

0 510

Jury Compromise

K - Jury Compromise 参考：ACM POJ 1015 Jury Compromise（陪审团的人选，动态规划题，难）说实话真有点难想，用一个DP[i][j]来表示在选取i个人，辩控差为j（j值已做些许处理）时辩控总分的最大值，用三个for循环来更新这个值。具体...

dp

2019-10-31

0 465

FatMouse's Speed

J - FatMouse's Speed DP的题写得多了慢慢也有了思路，虽然也还只是很简单的DP。因为需要输出所有选择的老鼠，所以刚开始的时候想利用状态压缩来储存所选择的老鼠，后面才发现n太大1<<1000根本存不下来... 思路的话其实也不难，把体重排序之后，对速度...

dp 最长有序子序列

2019-10-29

0 525

最少拦截系统

I - 最少拦截系统参考：ACM HDU 1257 最少拦截系统、思路：这个题其实是个贪心，每一次只需要找到一个离当前导弹高度最近的一个拦截系统进行拦截，即是最优解。代码： // Created by CAD on 2019/10/26. #include <...

贪心

2019-10-26

0 358

Tickets

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

dp

2019-10-26

0 386