已注销
已注销
全部文章
动态规划
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-1083-矩阵取数问题
ACM模版 描述 题解 经典的动态规划。 代码 #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int MAXN = 505;...
2021-05-22
0
279
51Nod-1007-正整数分组
ACM模版 描述 题解 被包装后的01背包。所有整数和最大为10000,所以只要求在sum/2的背包中,最大的价值,然后fabs(sum - dp[N][C] - dp[N][C])即为结果。 代码 #include <iostream> #include <algo...
2021-05-22
0
290
51Nod-1042-数字0~9的数量
ACM模版 描述 题解 数位dp,和51Nod 1009 数字1的数量是同类型题,方法一致。但是需要考虑的情况多了些,所以需要注意的细节也随之多了许多,一不小心,我就碰见了BUG,这个BUG,说起来好心酸,从七月找到了八月……问题在于这道题需要考虑到0的个数,而0的个数和其他的不一样,因为...
2021-05-22
0
240
51Nod-1050-循环数组最大子段和
ACM模版 描述 题解 这里分为两种情况: 其一:从[1, n]的正常顺序的最大子段和; 其二:从开头取一部分,结尾取一部分,中间舍去,那么中间的一定是最小子段和,然后所有数据的和减去最小子段和即可。 最后从两种情况中选取相对较大的情况。 代码 #include <iost...
2021-05-22
0
238
51Nod-1051-最大子矩阵和
ACM模版 描述 题解 这里需要格外注意的是,M和N分别指的是列数和行数,而不是行数和列数,这个能把你坑死……O(N^3)的复杂度可以过。 代码 #include <iostream> #include <cstdio> typedef long long l...
2021-05-22
0
305
HDU-5791-Two
ACM模版 描述 题解 类似于最长公共子序列问题,略微不同,另外需要考虑到重复状态的去重与否。 代码 #include <iostream> #include <cstdio> typedef long long ll; using namespace st...
2021-05-22
0
306
51Nod-1021-石子归并
ACM模版 描述 题解 动态规划,dp[a][b]:从a到b的最小合并代价和。 动态转移方程: dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + temp); 这里的temp是从j到i+j的和。 ...
2021-05-22
0
302
51Nod-1043-幸运号码
ACM模版 描述 题解 动态规划,dp[i][j]表示i个数和为j的总数(这里包括开头为0的情况),则: dp[i][j] = dp[i - 1][j - k](k:0 to 9) 最后,我们只需要用去掉0打头的情况*没有去掉0打头的情况累加并取模即可。 ans = (ans ...
2021-05-22
0
361
51Nod-1101-换零钱
ACM模版 描述 题解 类似于0-1背包问题,属于比较常见的动态规划。不同的是,这里是13种物件儿,不是13件物件儿。 代码 #include <iostream> #include <cstring> using namespace std; const ...
2021-05-22
0
318
51Nod-1268-和为K的组合
ACM模版 描述 题解 N比较小,深度优先搜索即可。 也可以使用动态规划,典型的0-1背包问题,可是K太大,正常情况会挂,然而这道题数据比较弱,K根本不到1e9的量级。 所以如果K的数据稍微一强,就会挂,可以优化超大背包,二进制枚举N/2个状态,然后筛选出所有可能存在的状态,最后再二进...
2021-05-21
0
300
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页