likeJ

动规dp

# Hash 和 Hash 表(1) # kmp 算法(1) # LCA（最近公共祖先）(1) # 二分(2) # 广搜bfs(16) # 树形dp(3) # 深搜dfs(8) # 贪心(4) # 递推(6) 1024程序员节(1) c++杂题(3) hash(4) STL(1) ST表(1) 二分图(5) 信息奥赛一本通——高效进阶(13) 单调栈(6) 单调队列(8) 图论(1) 并查集(9) 快速幂(2) 拓扑排序(6) 数论(2) 最小生成树(3) 最短路径(15) 未归档(4) 树状数组(4) 状态压缩(7) 矩阵乘法(2) 离散化(4) 线段树(5) 赛后分析(88) 邻接表(2)

/ 注册

全部文章 / 动规dp （共17篇）

Debug（树形dp）

Debug Description 经过了一整夜的激战，rc的部队终于攻下了虫族的首都Bugzilla。现在，rc决定亲自带领一队突击队员在虫族庞大的地道中寻找他的宿命之敌—Bug。　　Bugzilla由N个基地组成。这N个基地被N-1段双向地道连接在一起，每段地道都连接两个基地，并且保证任意...

2021-03-26

0 446

P2515 [HAOI2010]软件安装（树形dp）

软件安装题目传送门解题思路 1：这题可能形成环所以要缩点，用强连通分量 void sd()//缩点 { o=n; for(int i=1;i<=o;i++) for(int j=1;j<=o;j++) { if(a[i][j]==1&...

2021-03-26

0 531

鱼肉炸弹（树形dp）

鱼肉炸弹 Description 舒克和贝塔终于下定决心要去营救被关押在众猫聚居的A城中的大米同志。　　A城的构造是很奇怪的。A城中的所有N栋建筑沿着一条直线排列，而且没有两栋楼的高度是相同的。而大米同志就被关押在其中的某栋建筑中。每一栋建筑的顶上都是有一些猫们在看守的。如果按照从一端到另一端...

2021-03-26

0 414

SP39 PIGBANK - Piggy-Bank（dp）

SP39 PIGBANK - Piggy-Bank 题目传送门解题思路这题就是完全背包，只不过把max改为min就行了（再加个特判） AC代码 #include<iostream> #include<cstdio> using namespace std; lo...

2021-03-26

0 433

P1052 过河（状态压缩）

过河题目传送门解题思路这题就是状态压缩优化你可以先去看看P3951 小凯的疑惑（数论）从上题得知，a*b-a-b是最大不能得到的价值，后面的价值都能够得到这题也大同小异，当奇数和偶数都可以被枚举到时，后面的数自然也可以被枚举到最大能枚举到奇数和偶数的位置，就是T * (T-1...

2021-03-26

0 320

拦截导弹（最小路径覆盖）

拦截导弹 Description 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的...

2021-03-26

0 478

2020.9.12 SSL普及组模拟（第2题）（序列）（dp）

序列时间限制:1000MS 内存限制:128000KB 题目描述一个长度为k的整数序列b1，b2，…，bk（1≤b1≤b2≤…≤bk≤N）称为“好序列”当且仅当后一个数是前一个数的倍数，即bi+1是bi的倍数对任意的i（1≤i≤k-1）成立。给定N和k，请算出有多少个长度为k的“好序列”，...

2021-03-26

0 438