Bernard5

分类

作业(2) 学习笔记(17) 技术教程(45) 期末应试(57) 未归档(17) 赛后分析(7) 题解(132) 题集(15)

/ 注册

TA的专栏 160篇文章 0人订阅

算法竞赛之路

160篇文章 3594人学习

全部文章（共10篇）

最长公共子序列 Largest Common Subseqence 来自专栏

pecco #include <bits/stdc++.h> using namespace std; const int N = 1005; int dp[N][N]; // 可采用滚动数组优化只保留i/i-1行 string s, t; int main() { whil...

dp LCS 板子

2021-07-13

0 542

求DAG有向无环图直径 dp 来自专栏

动态规划对状态空间的遍历构成一张有向无环图，遍历顺序就是该有向无环图的一个拓扑序。 #include <bits/stdc++.h> #define sc(x) scanf("%d", &(x)) #define pr(x) printf("%d\n", (x)) #define...

图论 dp

2021-03-28

6 955

WZB's Harem 状压DP 来自专栏

状压DP 每一列对于每一行是唯一确定的，这一点契合了状态压缩的特性。出题人的话：一道状压 dp。首先不考虑皇后的差异性，把所有皇后当作是一样的，在第 i 行第 k 列安排一位皇后的方案数为 f[i][j|(1<<k)] += f[i][j]((j>>k)&1...

dp 状压DP

2021-01-20

3 693

小M和天平 bitset dp 来自专栏

bitset对dp的优化，非常典型 #include <bits/stdc++.h> using namespace std; const int N = 1e4; bitset<N + N + 100> b; int main() { int a, c; w...

STL 思维 dp bitset 位运算

2021-01-18

0 681

百度之星初赛1 - Dec 来自专栏

这一题是真正的DP，ZT大佬一开始想递归地去解决。这个是正向思维，然后程序就进死循环了。（可以从小到大递推，先对所有的数对判断是否互质，完成初始化。然后就是递推的关键：注意到必须满足从小到大递推的性质，所以要以主对角线为方向铺设。最后注意因为第一行（列）没有上一行（列），而且1与任何数互质，...

dp

2020-07-27

0 623

百度之星初赛 1 - GPA 来自专栏

一开始大家都没有想到，因为分布是不均匀的，所以这其实不是贪心。比如180的情况，最赚的是3.0。有点像背包，但也有点不一样。考虑DP，状态转移方程的核心在于枚举：把总分拆出来多少分，作为单独的一门课的成绩。 #include <bits/stdc++.h> #define sc(x) ...

dp

2020-07-27

0 1153

简单瞎搞题 BITSET 来自专栏

思路思路很简单就是用bitset来实现DP。本题数据最大为故开空间1e6。如果没有使用过bitset可以理解为一个bool数组。 bitset<N> ans声明，ans[i]的意思是是否能已知数据被表出，即最关键的DP分析在这里：for (int i = l; i <= r...

背包 STL dp bitset

2020-05-20

4 977

小V和方程来自专栏

分析考虑对质因数分解，并将提取成的最简形式。如果要满足，对于任意一个而言，化简后都带有。于是问题被转化成能被表示为多少种个数的和，其中可以有。也即个苹果放在个篮子里有多少种放法。此处可用dp解，表示个苹果放在个篮子里方法总数。转移方程为应牛友要求详细解释一下：把5个苹果放进2个篮...

数学 dp 排列组合

2020-05-15

2 970

张老师的旅行来自专栏

题意 n个点在数轴上排列，从其中一个点出发。每个点都有要求的最晚到达时间，问能否全部准时到达，如果能，给出完成时间。分析题目给出的n个景点是按照位置信息升序排列的。把起始点，即t为0的点设为k，所有的点分成了两部分：k点左边的点和k点右边的点。我们用一个数组dp[i][j][f]表示完成...

dp 区间DP

2020-05-13

0 669

I LOVE YOU 来自专栏

用dp来推断子序列个数 if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;统一小写，大小写不敏感。 dp[j] = dp[j] + (s[i] == a[j]) * dp[...

dp 字符串

2020-05-12

0 775