已注销
已注销
全部文章
动态规划
ACM模版篇(139)
C++(4)
CONTESTS(31)
dfs && bfs(59)
GitHub(1)
Linux(4)
OpenGL(2)
PHP(5)
Python(7)
QT(3)
Script(4)
STL(24)
位运算(3)
其他(37)
区间(22)
图形打印(6)
图论(96)
字符串(39)
打表(13)
排序(31)
数学相关(153)
数据结构(73)
数论(101)
暴力解题(31)
机器学习(10)
栈(14)
树(51)
每周都有那么几天不想学习(2)
汇编(6)
知识点总结(17)
笔试试题(15)
网络流(7)
职场老油条(1)
计算几何(17)
贪心(62)
逐梦者(97)
郑州-大连(2)
问题残余(4)
骑行也是追梦(1)
归档
标签
去牛客网
登录
/
注册
已注销的博客
元戎启行 赵闲(内推之星)
全部文章
/ 动态规划
(共148篇)
51Nod-1241-特殊的排序
ACM模版 描述 题解 猛一看这道题感觉似曾相识,好像以前做过一个只能往前插入的题,具体记不清楚了…… 这个问题实际上就是求最长等差数列(子序列)长度,要求 d = 1 即可,如此,复杂度只要为 O(n) 的动态规划就能搞定,get 到了新技能~~~ 如果要说为啥只要求最长……就可以得...
2021-05-21
0
365
51Nod-1274-最长递增路径
ACM模版 描述 题解 图上 dp,由于要求严格递增,所以需要先对边权进行排序,保证每次添加边权都递增,但是这样并不能保证严格递增,存在相同长度的边时,我们需要记录下来一同处理,保证他们在添加时互不影响,这样就没什么问题了。 代码 #include <cstdio> #in...
2021-05-21
0
340
51Nod-1296-有限制的排列
ACM模版 描述 题解 个人感觉,这个应该算是数位 dp。 先通过处理输入数据获取一个 state[],表示每相邻两项之间的大小关系,state[i] = 0,表示无特别关系,state[i] = 1 表示第 i 项小于第 i - 1 项,state[i] = 2 表示第 i 项大于第 ...
2021-05-21
0
182
51Nod-1310-Chandrima and XOR
ACM模版 描述 题解 讨论区大神已经说得十分详细了,我直接拿过来用吧…… 实际上这道题可以通过O((logn)^2)的时间推出任意一项。 我们以每一个2的整数次方作为分割点,把这个数列分割成很多块。设F(n)为2^n到2^(n+1)之间的所有满足要求的数字(不包括2^(n+1))。因为...
2021-05-21
0
308
ZOJ-The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple-E
ACM模版 描述 题解 典型的数位 dp,没什么太多可说的,注意前缀 0 不需要剔除。 代码 #include <cstdio> #include <iostream> using namespace std; typedef long long ll; ...
2021-05-21
0
287
CF-Tinkoff Challenge-Elimination Round-D-Presents in Bankopolis
ACM模版 描述 题解 没怎么做过树归问题,所以当做到这道题时不免有些懵逼。 典型的树归问题,从一个始发点不断查找下一个可行解,最后输出最小的可行解总和即可。 这么说是不是太随意了一些啊,毕竟我没有做出这道题。这个题并不算难,能想到动归就好办了。 首先我们设置一个 dp[st][ed...
2021-05-21
0
273
51Nod-1322-关于树的函数
ACM模版 描述 题解 典型的树归问题,复杂度 O(n2) 。 暂且不说树归部分,我们先考虑任何一种状态下如何求 S(e1,e2)2 。其实这里我们并不需要直接算出 A1、A2、B1、B2,只需要根据部分数据就能推出其他数据。 假如 A1 集合中有 n 个结点,那么 A2 集合中有...
2021-05-21
0
226
NYOJ-1249-物资调度
ACM模版 描述 题解 取与不取?这个值得思考?是不是很像01背包啊,不过不同的地方是,01背包是求能容最大价值,而这里是求能凑够 M 的方法数,其实很相似的,甚至更简单吧! 由于数据很弱,这个题其实用 dfs 搜索一下也可以解决,没什么大不了的,很水的一道题。 代码 #includ...
2021-05-21
0
241
NYOJ-1251-山区修路
ACM模版 描述 题解 每次看到 dp 问题都能知道是 dp,可是就是反应不过来如何 dp。 这次也是这样,找了找题解,算是搞明白怎么 dp 了。 根据题意我们可以知道,不管怎么调整,我们都可以通过把路的高度调整为一个已有的高度来实现结果最优。所以我们可以设,dp[i][j] 表示考虑...
2021-05-21
0
263
NYOJ-1255-Rectangles
ACM模版 描述 题解 矩阵嵌套问题,典型的 DAG 最长路问题。dp 搞搞就好。 代码 #include <iostream> #include <algorithm> #include <algorithm> #include <cstri...
2021-05-21
0
258
首页
上一页
2
3
4
5
6
7
8
9
10
11
下一页
末页