Z_L_G

分类

总结(20) 训练赛(14) 题解(108)

/ 注册

全部文章（共36篇）

算法入门-[NOIP2002]过河卒

题意 n*m的棋盘，卒在(0,0)，可以向右或者向下走，最终要走到(n,m)，同时，棋盘上还有一匹马，它会控制他能走到的8个点，以及它自己所在的位置,卒不能走这几个位置请问最终有多少条路径能让卒走到(n,m) 思路实现方法一：提前把不能走的点标一个极小值，转移方程为实现方法二：走到每一个...

dp

2025-06-27

0 26

算法入门-钉子和小球

题意一个竖直放置的三角形模板，钉着n(n+1)/2颗钉子，最底下有(n+1)个格子从最顶上落下一个小球，小球碰到钉子落向两边的概率相等求去除m个钉子后，落到最底下第m+1格的概率是多少，以a/b的形式输出思路概率不好处理，不妨认为小球每下落一层就分裂成两个，在有钉子的地方，一个去左边...

dp 概率

2025-06-27

0 32

算法入门-花店橱窗

题意花店有f朵花，v个盆，每个花放每个盆有不同的美观度，求如何摆放能使美观度最大特别的，给花编上号，花必须按照顺序摆放，编号小的的花不能放在编号大的花的后面思路由于必须按照顺序摆放，所以新的一盆花可放的盆一定是上一盆花放的盆的后面初始化:对于最开始，每朵花放在自己编号的盆里，其它...

dp

2025-06-27

0 22

算法入门-免费馅饼

题意在一个W*H的长方形平面内，有若干块饼下坠，每块饼会有{下坠时间，下坠位置，下坠速度，价值}四个信息人最初站在中间，可以移动(-2,-1,0,1,2)，请输出最多获得的价值以及开始后每一秒的操作思路这题有很多坑点显然是一个动态规划，状态转移方程坑点1:由于起点强制锁定在中间，但...

dp

2025-06-27

0 23

算法入门-舔狗舔到最后一无所有

题意每天可以从三家店中选一家，不能连续三天选同一家，t次询问，每次询问连续选n天有多少种不同的选择方案思路简单动态规划，显然第i天的可选择方案数取决于第i-1和第i-2天对于任意一个店，第i天可以选它的情况是第i-1天选另外两家，不用考虑第i-2天第i-1天选它，第i-2天只能...

dp

2025-06-24

0 30

算法入门-方块与收纳盒

题意走楼梯，斐波那契换了个描述思路水题，代码 #include<bits/stdc++.h> using namespace std; /** * dp[i]=dp[i-1]+dp[i-2] */ vector<long long> dp(100); in...

dp

2025-06-23

0 33

算法入门-树上子链

题意一颗有n个结点的树，每个结点具有权值，求解最长（权值最大）的一条子链思路对于某一个结点来思考，他能构成的最长子链无非下列集中情况之一包含他的最长链+最长的包含他一个儿子的最长链所有结点均为负值，最长子链自身的权值他自己的一条最长链（另一条全负）因此我们维护一个dp数组，...

树形dp dp 深度优先搜索

2025-05-19

0 51

算法入门-二叉苹果树(边权转点权)(补：两种做法)

题意对于一个有n个结点的二叉树，根的编号一定为1，每条边有权值求保留q条边时，最多能获得多少权值 tip:分析样例可以知道，这棵树的根是必须保留的，“剪枝行为”一定是保留根含有根的子树思路（法一）由于输入是无规律的输入每一条边，所以应当先建立起二叉树，从根开始深搜建树由于边权是较难处...

dp 树形dp 深度优先搜索

2025-05-16

0 45

算法入门-(USACO 2008 Jan G)Cell Phone Network(最小支配集)

最小支配集选择一个点，可以覆盖相邻的点，覆盖所有点所需最小选点题意给定一颗n个结点的树，求最小支配集思路考虑每一个点，他可能被支配的方式有：被父亲支配，选自己，被儿子支配，维护一个二维dp数组记录点和状态：自己：父亲：儿子：对于自己和父亲，状态方程很显然可以推出，对于...

dp 树形dp 深度优先搜索最小支配集

2025-05-16

0 41

算法入门-Strategic game(最小点覆盖)

最小点覆盖选择一个点，覆盖所有相邻边，最少选几个点能覆盖所有边题意给定一棵n个结点的树，选定一个结点后即可覆盖他的所有邻边，求覆盖所有邻边的最少选定结点数思路动态规划对于每一个结点，由于覆盖边，所以自己考虑选和不选两种情况，且父亲没选，自己就一定得选，父亲选了，自己就可选可不选...

dp 树形dp 深度优先搜索最小点覆盖

2025-05-15

0 34