博客主页：誓则盟约系列专栏：IT竞赛专栏关注博主，后期持续更新系列文章如果有错误感谢请大家批评指出，及时修改感谢大家点赞

01背包有N种物品，第i种物品的体积是v[i]，价值是w[i]，每件物品最多只能选1件。有一个容量为V的背包，问将哪些物品装入背包，可使这些物品的总体积不超过背包，并且总价值最大，输出最大价值。#include<bits/stdc++.h>usingi64=longlong;voidsolve(){intN,V;std::cin

存在和对于一切的语言importjava.util.Arrays;classSolution{publicbooleanwinnerSquareGame(intn){dp=newBoolean[n+1];dp2=newBoolean[n+1];Arrays.fill(dp,null);Arrays.fill(dp2,null);dp[0]=fa

如果我早点遇见你，结局是不是会不一样模板题链接很久没有写过这么长的代码了重要部分就是对倍增LCA的改动以下是代码，维护了最大边权和次大边权//Createdbyqyyon2024/6/4.#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#definePIIpai

LanqiaoOJ 773这道题是一道动态规划的题目，主要考察最长上升/下降子序列，难度中等，但是对思维的考察比较重要，特别是如何解决其第二问题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以

基环树算法总结一、什么是基环树基环树，顾名思义，有两个要素：环和树。因此，基环树就是一棵树的一个节点，扩成一个环，做题时，多棵基环树组成的基环树森林，常以如下方式出现：每个点只有一个出边。每个点只有一个入边。图中一共有\(n\)个点，\(n\)条边。那么，基环树类型的题目应该怎

数位dphttps://leetcode.cn/problems/reverse-bits-lcci/description/publicintreverseBits(intnum){intmax=0;intdp1=0;intdp2=0;for(inti=0;i<32;i++){if((num&1)==1){

一、问题描述P1020[NOIP1999提高组]导弹拦截二、问题简析该题要我们求两个问题：1、不上升子序列的最大长度2、不上升子序列的最少个数利用\(Dilworth\)定理，我们得到不上升子序列的最少个数等于上升子序列的最大长度。现在，就是求这两个问题：1、不上升子序列的最大长

P7914Solutionlink先考虑Subtask\(4\)。设\(dp_i\)表示长度为\(i\)的方案数，按题目定义转移:AB,ASB：\(\displaystyledp_n\getsdp_n+\sum_{i=1}^{n-1}\sum_{j=0}^kdp_i\timesdp_{n-i-j}\)(A)：\(\displaystyledp_n\getsdp_n+dp_{n-2}\)(SA),(AS)：\(\displa

2024，1，26今天做石子合并的题比较多贴一个模板 for(intlen=2;len<=n;len++){ for(inti=1，j;(j=i+len-1)<=n;i++){for(intk=i;k<j;k++){if(dp[i][j]>dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]){

B-CTZ难度:⭐题目大意给定一个数n,输出其二进制最后有几个连续的0;解题思路模拟一下就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespacestd;

Link一道很有意思的min-max博弈用树上dp来解决，那么显然的，当前节点是谁取的会影响答案，\(dp2_{i,j}\)表示取当前阶段，被Alice/Bob取走的结果，并且这个题是取子树上任意的节点，那么还需要保存子树上的信息，故使用\(dp_{i,j}\)记录下子树中的Alice/Bob取走的结果，然后就可以顺着dp解决这

基本情况A就开始犯病，导致+2.B、C都过样例了，但是都错。B.CircleGame赛时推出来奇数必输，也知道偶数不是必赢，但是思路不清楚。这里我没意识到一个很关键的性质。奇数堆拿的石堆会变，这也导致了必输，比如三个堆\(1,2,3\)。表粗的为JOE。123123显然JOE拿的石堆是变化的

DP2UVA12141LineChart先离散化一波，记位置从小到大第\(i\)个元素离散化后的大小为\(a_i\)。这题最大的难点就在于如何避免计重。如果现在要更新\(i\)位置的dp值，且\(\existsp<q,a_p=a_q\neqa_i\)，则贪心地考虑用\(q\)转移，而不是\(p\)，因为\(q\)位置结尾包

[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统

题目链接CSP考前做下历年真题。转移很多，我刚开始设$dp1[i][j]$为$i$到$j$合法的方案数，$dp2[i][j]$为左边一段$*$，右边是合法的方案数，以及$dp3[i][j]$，右边是$*$，左边合法。然后就进坑了，比如$()()()$，会在第二个位置统计一下，（两个合法的字符串拼起来）也会在第四个位置统计

难倒不难，128MB的空间限制快恶心死我了。我们设\(d_{u_0,u_1}\)表示到节点\((u_0,u_1)\)距离最近的叶子的距离，这个可以很容易换根DP求出。设\(p_{u_0}\)表示树\(u_0\)中距离最近的两个叶子的距离。设\(dis(u_0,u_1,v_0,v_1)\)（\(u_0=v_0\)）表示树中两个节点\(u_1\)和

洛谷传送门1.题目大意给定一个\(n*m\)的矩阵，矩阵中每个点\((i,j)\)都有一个权值\(f_{(i,j)}\)。每次可以向上，向下或向右走。问从\((1,1)\)走到\((n,m)\)，经过的路径上点的权值之和最大是多少？2.思路这道题我们不难想到动态规划。但是与一般的动规不同的是，本题中有上下右

ZJOI2008骑士自己写的时候建的是\(dls\)的反图,想的是基环树不是要保证每个点的出度为\(1\),就选择每个点向仇恨点连接一条有向边.这种情况下如果记录每一个点出度指向哪,那么在找环的时候不一定能找到,因为图上带环的话要根据入度点找环(画图理解)如果记录入度

一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。比方说，数组 [4,2,5,3] 的交替和为 (4+5)-(2+3)=4 。给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从0开始

Description552.StudentAttendanceRecordII(Hard)Anattendancerecordforastudentcanberepresentedasastringwhereeachcharactersignifieswhetherthestudentwasabsent,late,orpresentonthatday.Therecordonlycontainsthefollowingthre

题目：Theleastroundway 1000*1000的方阵，每个格子有一个非负整数，现在要从左上走到右下，每次只能向下或者向右走。目标是使得所有走的格子里的数的乘积里，末尾0的个数最少，要求输出最有解和走法。不用怎么想也知道基本是个dp了，可以发现其实只有2和5的因子是有用的，但是如果状态同时记

CunningGena-洛谷|计算机科学教育新生态(luogu.com.cn)ki表示显示器数量需求这点对于dp来说是比较难解决的，所以我们按k进行升序排序，这样便可以处理k的问题(其实这点有点难想到)。假设dp[i][j]为前i个物品，状态为j下的最小价格，那么转移的时候显然我们无法处理显示

A.TrustNobody题目大意给你一个长度为\(n\)的数组\(a\)，\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎，让你找出说谎的人的个数。思路：枚举说谎人数\(x\)，遍历\(a\)数组，对于当前\(a_i\)，如果有\(a_i\geqx\)，那么显然第\(i\)个人在说谎，记录人数看是否等

题目：给定一个长度为n，由非零整数成的数组，求连续子数组乘积为负数的个数example:55-33-1178ChatGPT的答案，基本正确，有个地方多+1了n=int(input())arr=list(