2022115828

学习笔记

题解(9)

/ 注册

全部文章 / 学习笔记（共4篇）

最大子段和问题

P1115 最大子段和思路：经典线性DP，dp[i]表示前i个元素的最大子段和，最后输出max(ma, dp[i])即可 void solve(){ int n; cin >> n; vector<int> a(n + 1), dp(n + 1); for(int...

C++ 动态规划双指针

2023-11-19

0 300

DP问题之背包问题

1：01背包问题问题：给出n个物品，每个物品只能使用一次，每个物品有相应的体积与价值，你可以选择总体积不超过m的物品放入背包，求能得到的最大价值思路：建立一个二维的DP矩阵，dp[i][j]表示把前i个物品装入体积为j的背包能得到的最大价值，从小问题扩展到大问题朴素版： int n, m; i...

C++ 动态规划

2023-10-20

0 278

KMP算法

KMP算法的作用：给你一个长为n的字符串s和一个长为m的字符串p，求s中等于p的连续子串的出现位置或者出现次数原理：当我们进行字符串匹配失配之后我们回溯到k，k满足从当前i位置的一个后缀等于适配字符串的一个k前缀，我们预先用nxt数组处理并且存储k的值，我们用p存储的是在当前位置能够适配字符串p的...

字符串匹配

2023-10-02

0 318

位运算技巧之拆位

1：Codeforces Round 900 (Div. 3) ：E. Iva & Pav 题意：给出一个长度为n的数组，给出一个l和k，求连续与运算之后找出最大的一个r，使得f(l,r)运算之后得出的结果大于等于k 思路：这里使用拆位的技巧，根据数据范围可知数字表示为二进制后最大不会超过3...

C++

2023-09-27

0 416