SSuryxin

分类

ACM个人赛题解(2) CF(1) dp(2) 图论(12) 数论(1) 笔记(5) 题解(29)

/ 注册

TA的专栏 3篇文章 0人订阅

3篇文章 1160人学习

全部文章（共7篇）

[ZJOI2007]最大半连通子图

[ZJOI2007]最大半连通子图题目描述：给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模思路：这是一个比较复杂的题？主要思路是：tarjan缩点+拓扑排序+dp 首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点...

链式前向星缩点 tarjan 拓扑排序 dp

2021-08-13

1 610

能量项链-区间dp 来自专栏

P1063 [NOIP2006 提高组] 能量项链题目描述：思路：区间dp 状态： dp[i] [j]表示合并i到j得到的最大能量转移方程： #include <cstdio> #include <cstring> #include <string>...

dp 区间dp

2021-05-12

0 745

前缀和+后缀最大值（dp）来自专栏

题目描述：今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间, 即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,......

后缀最大值 dp 前缀和

2021-05-11

0 1160

离散化dp 来自专栏

题目描述：在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥...

离散化 dp

2021-05-11

0 611

滑雪——记忆化搜索

滑雪题意：在二维数组中找到一条数字逐渐减小的最长的路径，输出路径长度思路：确定状态： dp[i] [j] 表示从（i，j）开始走的最长路径的长度原问题：从（1，1）到（n，m）任意一点开始走的最长路径的长度状态转移方程： dp[i] [j] = max{dp[i - 1] [j] + ...

记忆化搜索 dp

2021-03-11

2 630

传球游戏

题意： n个同学围成一个圆圈进行传球游戏，一个同学传球时只能传给左右的同学，传m次最终回到第一个人手里，问你有多少种情况？思路：第一步：确定状态——原问题是什么，子问题是什么？原问题：从1开始传球，第m步回到1号的情况数子问题：从1开始传球第i步到达j号的情况数 dp[i] [j]表示第i...

dp

2021-03-11

12 676

过河卒

过河卒题意：对于n * m的棋盘，棋盘中有九个点不能走，问你一个大头兵从左上角走到右下角的路径有多少条思路：使出秘技dp 状态转移方程是：tr[i] [j] = tr[i - 1] [j] + tr[i] [j - 1] 有一些细节： 🐎走的八个点的坐标得找对，同时得判这八个点是否符合题...

dp

2021-03-09

1 623