yizimi远欣

题解

其他(14) 算法及模板(3) 课内(2)

/ 注册

全部文章 / 题解（共3篇）

题解 P1736 【创意吃鱼法】

主要思路：二维DP + 二维前缀和我就讲讲我当时做这道题的想法就好了。如果你只拿了部分分，可以看看修改和优化方法。一开始我没看清题，一看，，，这不就是求最长的对角线吗（当时我还只以为是左上右下方向的对角线），，，好求啊，，，简单的dp就好啦当这个点有鱼时（a[i][j] ==...

DP

2018-12-02

0 493

题解 P1020 【导弹拦截】

题目某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次...

DP 线段树

2019-02-12

0 669

【题解】PAT 1003 Emergency

主要思路：Dijkstra + DP 如果做过最短路计数，这道题就相当于双倍经验了。就是在跑Dijkstra时，另计一个 \(t_i\) 作为到第 \(i\) 个点时最短路的条数，一个 \(rs_i\) 作为到第 \(i\) 个点最短路点权和的最大值注意一下维护条数时要分类，是...

DP 最短路 Dijkstra

2019-12-10

0 616