（一）非常妙的DP题，可惜被翻译毁了。题意：你有一堆零食，每个零食有两个值\(a_i\)和\(b_i\)。要求选出集合\(S\)，使\(\sum_{i\inS}a_i-\min_{i\inS}a_i\lep\)，求最大的\(\sum_{i\inS}b_i\)。一眼DP。先将\(a_i\)从小到大排序，每次循环更新\(dp_0\)的值为\(\max

CF13CSequence给定\(N\)个数，每次操作可以选其中一个数\(+1\)或\(-1\)。请问要让这个数列不降，最少需要多少次操作？我们用DP解决。对\(a\)从小到大排序，存在\(c\)中。我们用\(f[i][j]\)表示让前\(i\)个元素满足条件，而且这些元素最大值不超过\(c[j]\)的最小操作次数。状态转移方

暴力直接暴力枚举区间，并且逐个判断#include<iostream>#include<stdio.h>#include<algorithm>#include<string.h>#include<string>#include<cmath>#defineR(x)x=read()#defineFor(i,j,n)for(inti=j;i<=n;++i)using

题目传送门前置知识后缀数组简介解法一个子串出现至少\(2\)次等价于有至少连续\(2\)个后缀以这个子串作为公共前缀。进行一次后缀排序后，有\(\max\limits_{i=1}^{|s|}\{height_{i}\}\)即为所求。代码#include<bits/stdc++.h>usingnamespacestd;#definelllong

P2516[HAOI2010]最长公共子序列总的来说，这道题确实很精妙，难度也不小，耗费了不少时间去调。本来想过用容斥的思想，却因为当时理解不深没有继续思考就放弃了。学会了思路后对\(LCS\)有了更深层次的理解。题意简述给定\(A,B\)两个字符串（以.结尾），求它们的最长公共子序列的长度和个数

P5858「SWTR-3」GoldenSword第一道自己想出递推公式并且成功\(AC\)的\(dp\)绿题。题意简述有\(n\)种原料，每个原料有一个耐久度\(a[i]\)，必须按照\(1,2,…,n\)的顺序放入炼金锅。但是炼金锅的容量是有限的，只有\(w\)，所以在每次放入原料之前，都可以选择取出\(0\sims\)个原料再放

题目传送门前置知识概率DP|树形DP|RMQ解法观察到区间只有相离或包含关系，类似线段树的管辖区间，考虑将其构成树形关系。为方便代码书写，将原来的森林构成一棵树，即增加一个区间\(l_{q+1}=1,r_{q+1}=n,p_{q+1}=0\)。由于对于一个区间\([l,r]\)的最大值在经历任意次操作后，

不是很裸的01背包但是被卡了半天，所以记一下思路（？）对环的计算一般是从0-n-1，这样子转完一圈%n原位置就还是0，方便计算。然后二维dp，第一维表示第几次，第二维表示多少度。 #include<iostream>usingnamespacestd;intn,m;inta[5010];intf[5010][5010];intmain(){cin>

P4563[JXOI2018]守卫更好的阅读体验这道题让我充分认识了我一点不会dp。首先可以预处理一个点能看到的左边的所有点。注意到一个区间一定会选择右端点，设右端点不能看到的所有极长区间为\([l_1,r_1],[l_2,r_2]\dots[l_k,r_k]\)，区间\([L,R]\)的答案即为\(1+\sumf_{l_i,r_

更好的阅读体验CF1730FAlmostSorted挺有意思的一道题。刚看到可能有好几种思路，按照\(p\)的大小填\(q\)，或者按照下标顺序填等等。试了几次之后考虑按照\(i\)从小到大填入\(q_i\)，设\(pos\)为当前填了的最大的\(p_{q_i}\)，由于题目的要求，\(1\sim(pos-m-1)\)的所有数

postedon2022-08-1500:08:56|under题解|sourceproblem一个长为\(n\)的排列\(P\)，每次可以选择一个\(i\)，令\(v=\max(P_i,P_{i+1})\)，使\(P_i=P_{i+1}=v\)，求若干次操作后有多少种不同的序列。\(1\leqn\leq5000\)。solution显然地，对于一个\(P_i\)，它要么被完全覆盖

迷惑，开三道题发现T3见过原题没做。然后在kai586123老师课件里边找到了这题题号。震撼，震撼。不知道NJU营春测卡多少分。第一题正解是把询问对列分治，然后考虑跨过中间列的询问。暴力\(O(\dfrac{n^4}w+q)\)的方法是显然的，可以获得\(50-100\)分不等，略微卡常后通过。#in

PalindromeTimeLimit:4000/2000ms(Java/Other)   MemoryLimit:65536/32768K(Java/Other)TotalSubmission(s):72   AcceptedSubmission(s):19ProblemDescriptionApalindromeisasymmetricalstring,thatis,astringreadidenticallyfromle

postedon2022-09-2414:33:29|under题解|sourceproblem一个黑白矩阵，求以每个点为右下角，能围出的周长最大的全白矩形的周长。\(n\leq2000\)。solution试图进行

P5022[NOIP2018提高组]旅行我只想出了部分分的解法。。。https://fzy.blog.luogu.org/solution-p5022#include<bits/stdc++.h>#definefor1(i,a,b)for(inti=a;i

据joke3579说明，lyin做过今天的题但是给机会了。而且题目名称不管怎样都很吊。T1三分理论不对但是能过。但是场上把所有端点扒下来排序三分炸了。#include<cstdio>#inc