AROY

分类

不会DP的羸弱(1) 每日一题(29) 补题变更强(8)

/ 注册

全部文章（共38篇）

[每一][EA]双指针滑窗

https://ac.nowcoder.com/acm/problem/18386双指针滑窗的基本题型了模板： while(r<n){ window.push(); dosomething; while(window 不满足条件){ ...

2020-06-18

0 867

[哈理工程序竞赛]题解

哈理工 A race 签到题直接模拟，最大时间就是L/v2 #include <bits/stdc++.h> using namespace std; int main() { int v1,v2,t,s,L; cin>>v1>>v2>&g...

2020-06-16

0 693

[牛客练习赛65]补题

https://ac.nowcoder.com/acm/contest/5961 A 贪心瞎猜,小的用来加，大数用来乘 #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 5...

2020-06-15

0 566

[校赛dp]B题

不妨设dp[i] 代表选取的数字累加和模3 = i 的数字和假定nums[i] % 3 = 1 ，那么，和前面选取的数字和模 3 = 2 的数相加，就可以模3为 0 ，表达起来就是 dp[0] = max(dp[0], nums[i] + dp[2])依次类推，只要不断更新 dp 数组即可

2020-06-13

0 532

[练习赛]DP--A题

https://ac.nowcoder.com/acm/contest/5968/A登上天梯必须要按照它要求的方法，否则就无法登上。它要求的方法为： 1．可以直接登上比当前位置高1个单位高度的天梯。 2．可以从当前阶梯往下退一级天梯（第一级天梯除外）。 3．在连续退k步后，跳跃一次...

2020-06-12

0 658

[练习]DP-背包类

https://ac.nowcoder.com/acm/contest/5968/E选出来要买的m个物品中任意两个的位置差都大于等于k就行了。现在告诉你这n个物品排成一行之后的受欢迎程度（可能是负数），求牛牛带回去的m个物品的最大欢迎度之和。错误写法：(记录一下思考过程 int a[N]; in...

2020-06-12

0 745

[每一]DP-类似背包

https://ac.nowcoder.com/acm/problem/19158 每件武器只有三种选择：放在左边，或者放在右边，或者不放对应着也就三种状态转移，考虑背包思想dp[i][j] 表示前i个左右重量差为j的最大重量则状态转移为：不选：选：考虑质量差最大是所有武器重量总和，最小是0代...

2020-06-10

0 731

[每一]树形DP，最大独立子集

https://ac.nowcoder.com/acm/problem/15748最大独立子集：选出尽量多的点，使得任何两个节点均不相邻，输出一个最大独立集。最大独立子集 f[i][0/1]表示以i为根时最大独立点的数量，f[][0]--不住 f[][1]--住则初始值为1， v是u的儿子节点...

2020-06-08

0 1011

【每一】双BFS板子

https://ac.nowcoder.com/acm/problem/23486 这题属于双BFS模板题A一个队列进行BFS B一个队列进行BFS两者同时进行BFS----B走两步 A走一步BFS过程中判断A是否走到了B走过的点（vis数组判断即可）即： while(!que[0].empty(...

2020-06-08

0 829

【每日一题】[SCOI2005]最大子矩阵 (DP)

https://ac.nowcoder.com/acm/problem/20242有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠先看 m , m 只有 1 和 2先考虑简单情况----m=1 即一维最大子矩阵状态定义:f[i][l]...

2020-06-08

1 779