iiiiikun
iiiiikun
全部文章
dp
bfs(11)
codeforce(2)
codeforces(49)
dfs(27)
icpc(2)
kmp(2)
kruskal(1)
min25(1)
spfa(3)
stl(3)
三分(1)
二分(11)
二分图(3)
二叉树(2)
二叉树遍历(1)
倍增(1)
几何(1)
前缀和(6)
剪枝(1)
动态规划(2)
单调栈(1)
博弈论(1)
双指针算法(1)
双端队列(1)
唯一分解定理(1)
回文(1)
图论(4)
堆(1)
字符串(2)
尺取法(1)
差分(4)
差分约束(1)
并查集(7)
循环节(1)
快速幂(3)
思维(5)
思维题(6)
拓扑排序(2)
排序(1)
数位dp(3)
数位交换(1)
数学题(1)
数据结构(7)
数论(17)
最大子矩阵(2)
最小生成树(8)
最短路(17)
最长公共上升子序列(1)
有向图强联通分量(4)
未归档(8)
权值线段树(2)
构造(2)
枚举(2)
栈(1)
树形dp(4)
树状数组(3)
树的直径(1)
概率(1)
模拟(1)
模拟赛(1)
模拟退火(1)
模板(9)
欧几里得(1)
欧拉回路欧拉路径(1)
牛客多校(1)
状态压缩(1)
矩形面积(1)
矩阵乘法(1)
矩阵快速幂(1)
离散化(1)
筛素数(1)
线段树(4)
网络流(3)
背包(1)
菜鸟(14)
蓝桥(23)
蓝桥杯(2)
蓝桥训练(2)
贪心(11)
递归(1)
递推(2)
链表(2)
队列(3)
题解(2)
马拉车(2)
高精度(1)
归档
标签
去牛客网
登录
/
注册
iiiiikun的博客
老废物了
全部文章
/ dp
(共65篇)
acwing 1064. 骑士
在 n×n 的棋盘上放 k 个国王,国王可攻击相邻的 8个格子,求使它们无法互相攻击的方案总数。 输入格式 共一行,包含两个整数 n和 k。 输出格式 共一行,表示方案总数,若不能够放置则输出0。 数据范围 1≤n≤10, 0≤k≤n^2 输入样例: 3 2 输出样例: 16 ...
2020-12-17
0
0
1068. 环形石子合并
解题报告:之前做过线形的石子合并,现在做这题看了y总的思路,可以通过扩增一倍的数组,枚举长度为n的合并值取最大值和最小值就行啦。 #include<iostream> #include<cstring> using namespace std; const int N=...
2020-12-17
0
380
320. 能量项链
解题报告:这道题和环形石子合并唯一的不同就是这道题枚举长度枚举到n+1,比如 2 3 4 5 这个样例, 实际上 他是 2 3 4 5 2 3 4 5,f[l][r]代表把l,r区间合并的最大值,枚举裂开的点,f[l][k]+f[k][r]+w[l]*w[r]*w[k],注意这里k不能和l或者r重合...
2020-12-17
0
383
AcWing 1057. 股票买卖 IV
解题报告:这道题是个状态机模型的简单题吧,主要题目的细节是买入卖出加起来算是一笔交易,状态转移也不说了,注意一下j-1和j的区别,f[i][j][k]代表前i天的股票已经进行了j次交易,k为0代表当前手里没有股票,k=1时代表手中有股票,初始化把交易次数为0并且手中没有股票的方案都变为0,别的都是非...
2020-12-17
0
479
Acwing 1075. 数字转换
解题报告:这道题其实就是树形dp的板子题,还掺杂着一点数论的气息,如果朴素去枚举每个数的最大公约数用试除法,o(n根号n),如果n大点就不行了,可以用线性筛的思想,去枚举每个公约数,把他的>=2倍都加上它,这样做法线性On的。然后dfs任意一个节点,找最大距离就可以了。 #include&l...
2020-12-17
0
400
1074. 二叉苹果树
解题报告:这道题也是树形dp题,f[i][j]代表根节点是i的情况下留j条边的最大值的方案,最后要求的是以1为根最大值为q的方案,状态转移方程就是类似于分组背包问题,先从大到小枚举体积,再枚举给子树的体积. #include<iostream> #include<cstring&...
2020-12-17
0
403
皇宫看守(树形dp)
解题报告:其实这题就是没有上司的舞会和战略游戏的翻版,,类似于状态机f[u][j] 以u为根节点,j有0,1,2,分别表示被父节点侦察到,被子节点侦察到,自己身上放守卫。 #include<iostream> #include<cstring> using namespac...
2020-12-17
0
362
区间dp
解题报告: 这题看了y总的解说是区间dp类型的题目,f[l][r]代表把l到r之间的多边形划分成三角形的最大方案。 其中状态转移就是f[l][r]=min(f[l][r],f[l][k]+f[k][r]+w[l]*w[r]*w[k])(k<r&&k>l),然后再套一点大数...
2020-12-17
0
386
最长不递减子序列
解题报告:哎。。。我蒟蒻啊,这都没看出来,我以为是线段树的题,结果是dp题,就是算出最长非降序子序列的长度len,然后n-len就行了。 #include<iostream> #include<algorithm> #include<cstdio> #inclu...
2020-12-17
0
406
P1279 字串距离
题目描述 设有字符串X,我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串,如字符串X为”abcbcd”,则字符串“abcb□cd”,“□a□bcbcd□”和“abcb□cd□”都是X的扩展串,这里“□”代表空格字符。 如果A1是字符串A的扩展串,B1是字符串B的扩展串,A1与B1...
2020-12-17
0
451
首页
上一页
1
2
3
4
5
6
7
下一页
末页