洛谷P4302 [SCOI2003]字符串折叠(区间dp)
题意 "题目链接" Sol 裸的区间dp。 转移的时候枚举一下断点。然后判断一下区间内的字符串是否循环即可 cpp include define Pair pair define MP(x, y) make_pair(x, y) define fi first define se second de ...
程序员文章站2022-10-06cf1139D. Steps to One(dp)
题意 "题目链接" 从$[1, M]$中随机选数，问使得所有数gcd=1的期望步数 Sol 一个很显然的思路是设$f[i]$表示当前数为$i$，期望的操作轮数，转移的时候直接枚举gcd $f[i] = 1 + \frac{ \sum_{j=1}^N f[gcd(i, j)]}{N}$ 然后移一下项就 ...
程序员文章站2022-10-06BZOJ2023: [Usaco2005 Nov]Ant Counting 数蚂蚁(dp)
题意 题目描述的很清楚。。。 有一天，贝茜无聊地坐在蚂蚁洞前看蚂蚁们进进出出地搬运食物．很快贝茜发现有些蚂蚁长得几乎一模一样，于是她认为那些蚂蚁是兄弟，也就是说它们是同一个家族里的成员．她也发现整个蚂蚁群里有时只有一只出来觅食，有时是几只，有时干脆整个蚁群一起出来．这样一来，蚂蚁们出行觅食时的组队方 ...
程序员文章站2022-10-05BZOJ1093: [ZJOI2007]最大半连通子图(tarjan dp)
题意 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：?u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V，E'是E中所有跟V'有关的边，则称G'是G的一个导出子图。若G'是G的 ...
程序员文章站2022-10-05洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)
题意 满足$b_1 < b_2 < \dots < b_k$且$a_{b_1} \geqslant a_{b_2} \geqslant \dots \geqslant a_{b_k}$ Sol 组合数取模？ 肯定考虑Lucas定理 考虑Lucas定理在最后一步肯定会化为$C(1, 1), C(1, ...
程序员文章站2022-10-05IT编程暑假DP动态规划练习
1.https://cn.vjudge.net/problem/12304/origin POJ 3176 从上往下走或者右下走找最大总和，也可以不同dp写。 注意动态规划这一步一定是和上一步或下一步有关联的 全部代码 2.https://cn.vjudge.net/problem/30465/or ...
程序员文章站2022-10-04洛谷P2704 [NOI2001]炮兵阵地(状压dp)
题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示 ...
程序员文章站2022-10-04IT编程洛谷P1523 旅行商简化版(DP)
题目： "P1523 旅行商简化版" 解析 可以看做是两个人同时从西往东走，经过不一样的点，走到最东头的方案数 设$f[i][j]$表示一个人走到i，一个人走到j的最短距离（$i using namespace std; const int N = 1010; int n, m; double f[ ...
程序员文章站2022-10-04LeetCode 1230. 抛掷硬币（DP）
文章目录1. 题目2. 解题1. 题目有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。请对每一枚硬币抛掷 一次，然后返回正面朝上的硬币数等于 target 的概率。示例 1：输入：prob = [0.4], target = 1输出：0.40000示例 2：输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0输出：0.03125 提示：1
程序员文章站2022-10-03IT编程Win10 2004版蓝牙A2DP在哪? Win10蓝牙A2DP动能的使用方法
Win10 2004版蓝牙A2DP怎么用?？想要将手机上的歌曲在电脑上播放，我们可以哦通过Win10 2004版新增的蓝牙A2DP功能实现，下面我们就来看看详细的教程，需要的朋友可以参考下... 20-06-11
程序员文章站2022-09-30科技P1108 低价购买 (DP)
题目 "P1108 低价购买" 解析 这题做的我身心俱惫，差点自闭。 当我WA了N发后，终于明白了这句话的意思 当二种方案“看起来一样”时（就是说它们构成的价格队列一样的时候）,这2种方案被认为是相同的。 这题有两问，第一问显然最长严格下降子序列，一看数据范围：5000，跟最长严格上升子序列一样，$ ...
程序员文章站2022-09-28BZOJ3687: 简单题(dp+bitset)
Description 小呆开始研究集合论了，他提出了关于一个数集四个问题：1．子集的异或和的算术和。2．子集的异或和的异或和。3．子集的算术和的算术和。4．子集的算术和的异或和。 目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把这个问题交给你，未来的集训队队员来实现。 小 ...
程序员文章站2022-09-26【线性 dp】A005_LC_不同的子序列（记忆化 / dp 分类讨论）
一、Problem给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。题目数据保证答案符合 32 位带符号整数范围。示例 1：输入：S = "rabbbit", T = "rabbit"输出：3解释：如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。(上箭头符号 ^ 表示选取的字母)rabbbit^^^^ ^^rabbbit^^ ^^^^rabbbit^^^ ^^^二、Solution方法一：记忆化思路问题本质是抽出 s
程序员文章站2022-09-24清华学霸提灯给你讲解DP，听不懂你打我
最近九章算法和阿里云合办了一场在线编程大赛，根据赛后数据显示，超过70%的选手认为动态规划是最难对付的题型。而自从动态规划出现在算法面试后，同样成为求职者绕不开的“噩梦”。除了Google，TikTok等常面DP的大厂外，现在就连亚麻电面阶段也考DP了，如果没有准备的话，分分钟就可能挂面。动态规划的...
程序员文章站2022-09-21IT编程HDU4089 Activation(困难的循环期望dp)
传送门啊啊啊啊啊啊啊啊啊啊啊解题思路摘自kuangbin博客题意：有n个人排队等着在官网上激活游戏。Tomato排在第m个。对于队列中的第一个人。有一下情况：1、激活失败，留在队列中等待下一次激活（概率为p1)2、失去连接，出队列，然后排在队列的最后（概率为p2）3、激活成功，离开队列（概率为p3）...
程序员文章站2022-09-21石子合并2——环状合并DP
题目描述在一个环形跑道上有N堆石子，每次取相邻两堆进行合并最终合并成为一堆。请问将每次合并后的代价进行累加其总和最少为多少输入第一行为石子堆数N,N...
程序员文章站2022-09-21IT编程【状压dp】[HDU1400 & poj2411] Mondriaan‘s Dream
对于棋盘上每个点，都有几种可能，1.不放 2.横放的前一个 3.横放的后一个 4.竖放的上一个 5.竖放的下一个由于题目要求每个格子都被填满，所以可能1不存在然后，我们可以考虑用1表示这个格子被放上了2/3/5这几种可能，然后通过二级制压缩状态对于每一行都有一个数值来表示当前行的状态 now 以及上...
程序员文章站2022-09-21完全背包&&区间dp&&最长上升子序列（南昌理工学院ACM集训队）
做了许多动态规划题目，结合yxc大大的视频，总结了一点动态规划模板，用几道经典例题加以解释dp 第一步——状态表示（dp[i][]j）； 个人感觉一道动态规划题最难的一步就是状态表示，有一个清晰直观的状态表示做题时便势如破竹。状态标识包括集合和属性两点，集合是题目中的各个要素结合所形成的状态，属性则...
程序员文章站2022-09-172020牛客暑期多校训练营Groundhog and Apple Tree(树形dp，贪心)
Groundhog and Apple Tree题目描述样例input:154 2 1 5 71 2 41 3 54 2 95 2 3output:23题目大意给定一棵树，每条边有权值，点上也有权值。现有一个初始Hp=0Hp=0Hp=0的人，如果经过边，那么HpHpHp减去边权，如果经过点，那么会加...
程序员文章站2022-09-17IT编程2020暑期牛客多校训练营第九场（K）The Flee Plan of Groundhog（lca，树形dp）
The Flee Plan of Groundhog原题请看这里题目描述：疫情爆发后，土拨鼠格外小心，因此他提早在1st1 ^ {st}1st卧室戴上口罩，然后走到nth{n ^ {th}}nth宿舍的路上与奥兰治一起玩。 ZLZXZLZXZLZX中有n{n}n个宿舍，它们通过n−1{n-1}n−1条走廊相连。每个宿舍可以互相到达。每个走廊的长度为1{1}1。土拨鼠的步行速度为1m/s{1 \ \mathrm {m / s}}1m/s。那时有个坏消息来了：土拨鼠出发t{t}t
程序员文章站2022-09-17移动技术