数列分段 Section II
二分答案；
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define mem(vis, num) memset(vis, num, sizeof(vis));
using namespace ……继续阅读 »
yanzexi
1年前 (2023-11-29) 378浏览 0评论
0个赞
求和
因式分解加前缀和；
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M = 200010;
int a[M], n;
ll pre[M], ans;
int main(){
memset(pre, 0, s……继续阅读 »
yanzexi
1年前 (2023-11-25) 287浏览 0评论
0个赞
零钱兑换
完全背包问题；
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
vector<int> dp(amount + 1, a……继续阅读 »
yanzexi
1年前 (2023-11-23) 242浏览 0评论
0个赞
环形链表 2
快慢指针，相遇有环，遇后快停，慢头同走，相遇入口；
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *f = head, *s = head;
while(f && f -&g……继续阅读 »
yanzexi
1年前 (2023-11-18) 317浏览 0评论
0个赞
柱状图中的最大矩形
$l$数组存储第$i$个数左边第一个小于$i$高度的索引，$r$数组存储第$i$个数右边第一个小于$i$高度的索引；
class Solution {
public:
int largestRectangleArea(vector<int>& heights){
int ……继续阅读 »
yanzexi
1年前 (2023-11-16) 335浏览 0评论
0个赞
最长有效括号
状态定义为以 i 结尾的最长有效括号长度；
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if(n == 0 || n == 1){
……继续阅读 »
yanzexi
1年前 (2023-11-14) 279浏览 0评论
0个赞
快速幂-慢速乘
//快速幂
long long q_poe(long long x, long long n, long long mod){
long long res = 1;
while(n > 0){
if(n & 1) {
res = (res * x) % m;
}
x = (x * ……继续阅读 »
yanzexi
1年前 (2023-11-08) 285浏览 0评论
0个赞
最优二叉搜索树
//最优二叉搜索树
double dp[MaxN + 1][MaxN + 1], w[MaxN + 1][MaxN + 1];
int s[MaxN + 1][MaxN + 1];
double OptimalBinarySearchTree(vector<double>& p, vector<double>& q){
int n =……继续阅读 »
yanzexi
1年前 (2023-11-07) 358浏览 0评论
0个赞
今天补趣学算法（陈小玉）的内容，好家伙没看过的的全是区间 DP。
游船租赁
//游船租赁
int YachtLeasing(vector<vector<int> >& r, int a, int b){
int n = r.size();
int dp[n + 1][n + 1];
……继续阅读 »
yanzexi
1年前 (2023-11-06) 401浏览 0评论
0个赞
旅行商问题
//旅行商问题
//dp[S][v]表示在 S 已被访问时从 v 出发访问的最小值
//递归版
int n;
vector<vector<int> > d;
int dp[1 << MaxN][MaxN];
memset(dp, -1, sizeof(dp));
int TSP(int S, int v){
if(dp[S][v] ……继续阅读 »
yanzexi
1年前 (2023-11-05) 370浏览 0评论
1个赞
