DP
  • 2024-07-231258:【例9.2】数字金字塔
    1.题目描述题目。。。是这样的来!\(3!2!1!\)上链接!我是链接2.分析从下往上开始,最大的是\(24\),有两条路可走,就走大的那一个\(15\)以此判断,最后加上\(13\)便为\(13+8+26+15+24=86\)果然,dp大法好!Q:dp是什么?A:动态规划Q:动态规划是什么?A:自行百度我是另一个链接3.代码
  • 2024-07-222024牛客暑期多校训练营2(部分题目题解)
    2024牛客暑期多校训练营2(部分题目题解)C.RedWalkingonGrid题意:给定只有红白的2*n个格子,只能走红色各自且只能上下左右走,问最多可以走多少红色格子。题解:左右走:dp[0][i]=dp[0][i-1]+1;上下走:intk1=dp[0][i];intk2=dp[1][i];dp[0][i]=max(dp[0][i],k2+
  • 2024-07-222024牛客暑期多校训练营2
    2024牛客暑期多校训练营2E-GCDVSXOR_2024牛客暑期多校训练营2(nowcoder.com)题意给定x,构造y<x使得gcd(x,y)=x⊕y思路取x−lowbit(x)即可,如果x是2的整数次幂则无解。代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;voi
  • 2024-07-22Luogu P4310 绝世好题 题解 [ 绿 ] [ 线性 dp ] [ 单调队列优化 ] [ 二进制优化 ]
    题目:绝世好题。暴力dp显然\(O(n^2)\)转移即可。单调队列优化观察到只有某二进制位两个数都为\(1\)时才能转移,因此我们把每个二进制位开一个单调队列,然后对于一个数\(a\),找到它是\(1\)的二进制位并选其单调队列的队头进行转移,在这之后把这个数加入符合要求的单调队列
  • 2024-07-22Codeforces Round 957 (Div. 3)复盘
    今天打了一下DIV3,专业转了就是不一样T1Onlypluses这道题主要就是理解乘法分配律,最多的绝对是两数相乘数最大的。T2AngryMonkey这道题一遍AC,虽然很简单还是值得鼓励,主要还是数学问题,用笔写下来找到数学规律之后做起来就很快T3GorillaandPermutation这道题还是很简单
  • 2024-07-22片集 - DP - 1
    欢迎来看“片”(的简介)由于-\(看片\)-生涯转瞬即逝,于是我选择对“\(片\)”进行一定的总结:相信你一定看懂了由于开始的时间有一点晚,就姑且认为我以后会慢慢补充吧......\(CF1789F\)\(Serval\)\(and\)\(Brain\)\(Power\)解:DP见过狗的,没见过这么狗的:分\(3\)类讨论:首先
  • 2024-07-22树形dp
    含义顾名思义,在树上dp,一般要分类讨论,在dfs中做dp 没有上司的舞会https://www.luogu.com.cn/problem/P1352 Ural大学有N名职员,编号为1∼N。他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。每个职员有一个快乐指数,用整数Hi给出,其中1≤i≤N。
  • 2024-07-22P3089 [USACO13NOV] Pogo-Cow S
    原题链接题解暴力dp:遍历\(i,j,k\),\(dp[i][j]=\max(dp[j][k])+v_i\)其中\(x_i-x_j\geqx_j-x_k\)优化:对于\(j\)来说,随着\(i\)越大,\(k\)可以越小,因此省去了遍历一层\(k\),而是维护每个点的\(k\),(反正求的是最大值)细节1.有两个方向2.任意起点code#include<bit
  • 2024-07-22P3572 [POI2014] PTA-Little Bird
    原题链接题解首先,考虑接下来往哪颗树飞是很困难的,因为当前的决策会影响之后的决策但是如果考虑到达当前树从哪里飞过来就比较好了,因为无后效性接着我们可以暴力做法,遍历每棵树从前\(k\)个树飞过来的值,然后取最小的那个,但是这样显然会超时,所以我们优化一下有哪些值得被优化
  • 2024-07-22dp乱刷
    CF1271DPortals思维点:每个城堡可以在其最晚可以被派遣到的时间被派遣,因为在最晚时间之前派遣的方案可以直接变为对应的在最晚时间派遣的方案。然后尽情DP即可。P1450[HAOI2008]硬币购物巧妙的容斥。首先按无限背包做,然后减去某一种硬币\(i\)超额的方案数,即\(f[s-(d_i+1)*c_
  • 2024-07-22【动态规划】【官解+整洁度优化+状态压缩-空间优化算法】力扣198.打家劫舍
    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组,计算你不触动警报装置的情况下,一夜
  • 2024-07-22代码随想录算法训练营第36天 | 动态规划基础2:62.不同路径、63.不同路径 II
    62.不同路径https://leetcode.cn/problems/unique-paths/submissions/548656029/代码随想录https://programmercarl.com/0062.不同路径.html63.不同路径IIhttps://leetcode.cn/problems/unique-paths-ii/description/代码随想录https://programmercarl.com/0063.不同路径
  • 2024-07-22力扣-动态规划全解
    目录动态规划斐波那契数列-EASY爬楼梯-EASY使用最小花费爬楼梯-EASY不同路径-Middle不同路径II-Middle不同路径III-HARD整数拆分-MID*不同的二叉搜索树-MID背包问题-理论基础分割等和子集-EASY最后一块石头的重量II-MID目标和-MID*一和零-MID*53-最大子数组和-中等918-环形子数
  • 2024-07-22基环树
    基环树一棵树多了一条边。。。就变成了基环树。首先把这个环找出来,对于这个环,断掉一条边就变成树了,固定一个端点跑树形dp。城市环路很板子,没坑点。找环可以用并查集,不用知道具体有哪些点。我们只需要找出其中一条边的两个端点作为断点就好了。for(inti=1;i<=n;i++){ int
  • 2024-07-227.15-7.21 总结
    做题:主要完成了一些https://www.luogu.com/article/ki71nw88中的dp题目和Eltaos_xingyu的dp。题目不算非常困难。学习:学习了Pfaffian和线段树分裂和Trie树全局+1的Trick。开始了《HandbookofEnumerativeCombinatorics》一本书的阅读,是一本组合计数的书。获得
  • 2024-07-22洛谷算法题
    目录数字反转迪杰斯特拉算法背包问题字符串排序P1192台阶问题P1111修复公路炸铁路问题计数问题
  • 2024-07-21区间dp入门
    [NOI1995]石子合并题目描述在一个圆形操场的四周摆放\(N\)堆石子,现要将石子有次序地合并成一堆,规定每次只能选相邻的\(2\)堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。试设计出一个算法,计算出将\(N\)堆石子合并成\(1\)堆的最小得分和最大得分。输入格
  • 2024-07-21【普及动规】dp例题精讲+强化练习
    本篇给大家带来一些好的dp题,大家可以学习一下。找找感觉。dp这种东西主要还是靠分类总结+感觉。多练习永远不错。T1.害羞的xxx题面:(由于某些原因无法公开原题,请见谅)题目背景保护好xxx,因为他随时会害羞。题目描述众所周知,xxx非常害羞。可是学校最近在选拔芭蕾舞演员
  • 2024-07-21HDU多校 2024R1
    T1把\(A\)的所有循环位移哈希一下扔set里,拿\(B\)的所有长为\(|A|\)的子串查一遍即可。代码#include<iostream>#include<set>usingnamespacestd;set<unsignedlonglong>st;constintB=2333;unsignedlonglongpw[2000005];intmain(){inttc;
  • 2024-07-21核电站问题
    题目描述核电站问题一个核电站有N个放核物质的坑,坑排列在一条直线上。如果连续M个坑中放入核物质,则会发生爆炸,于是,在某些坑中可能不放核物质。任务:对于给定的N和M,求不发生爆炸的放置核物质的方案总数。输入输出格式输入格式:输入文件只一行,两个正整数N,M(1
  • 2024-07-21CF1720D2
    感觉静下来能想出来?整个思路没有太容易走偏的地方,就最后一段有点难首先看到异或想到01trie和拆位,然后看到要求最长子序列,想到dp。所以目前的想法就是01trie里存dp,然后按照某种方式找到最大的,来更新\(dp_{i}\)。不会了!\(a_{i}\oplusj>a_{j}\oplusi\)怎么搞啊。我们拆位,发现如
  • 2024-07-21NOI 2024
    省流:100+264+180=544,rk45极限进队。赛前状态感觉还行,gzy天天在模拟赛里爆标,给他磕头了。day0开幕式。很想喷【】【】【】【】【】【】,算了不喷了。笔试,开场10s大家就开始笑,笔试把答案发下来了。”我们题目的配置出了一点问题,大家稍安勿躁“。致敬传奇出题人。推迟15
  • 2024-07-21E. Rudolf and k Bridges
    链接https://codeforces.com/problemset/problem/1941/E题目思路比较容易想到的一道题(但是之前想了好久hhh)。首先题意是对一连串的桥的代价求和,不难想到是前缀和求区间最小。那么就可以拆分这题为每行处理。容易想到dp,而且dp的过程也比较简单:设dp[i]是到达i的最小代价,那么对
  • 2024-07-21算法随笔——DP优化
    单调队列优化DP单调队列模板:inthead=1,tail=0; for(inti=1;i<=n;i++) { while(head<=tail&&head不满足条件)head++;//踢出队列 f[i]=f[q[head]]+...; while(head<=tail&&tail与i不满足单调性)tail--; q[++tail]=i; }优化思路则是
  • 2024-07-21[NOIP2005 普及组] 采药
    题目描述辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值