DP是个啥？（三）

6.区间与环形DP问题我们来看一道经典的问题：【NOI1995】P1880 石子合并题面：圆形操场的四周摆放 NNN 堆石子，现要将石子有次序地合并为一堆。每次只能选择两个相邻的石子堆合并成新的一堆，并将新的一堆的石子个数记为该次合并的...

DP是个啥？（二）

5.背包问题在动态规划问题中，有一个非常经典的问题：给定 nnn 个物品，每个物品都有它的重量 wiw_iwi 和价值 viv_ivi，给定限重，求获得的最大价值。比如说，如果有三个物品，重量分别为 3,4,53,4,53,4,5，价...

Day 1 共有十道单项选择题。以下简称“第X题”为 f(X)。这道题的答案是：A.A B.B C.C D.D 第五题的答案是：A.C B.D C.A D.B 以下选项中哪一题的答案与其它三项不同：A.f(3) B.f(6) C.f(2...

1.概念 DP 即动态规划(D\color{red}{\text{D}}Dynamic\color{black}{\text{ynamic}}ynamic P\color{red}{\text{P}}Programming\color{b...

T3.最小环题面：给定一个长度为 nnn 的正整数序列 aia_iai，下标从 111 开始编号。我们将该序列视为一个首尾相邻的环，更具体地，对于下标为 i,j(i≤j)i,j(i\le j)i,j(i≤j) 的两个数 ai,aja_...

介绍这次的 NOI Online 可以说是非常难了，可以说入门组的难度已经和提高组持平。不过提高组的三道题都是很有技术含量的，需要长时间的思考才能得出正解，这也体现了提高组应有的风格。下面我们还是按照入门组研究题目的方法，硬干一下提高组...

T2.冒泡排序题面：给定一个 1−n1-n1−n 的序列 pip_ipi，接下来有 mmm 次操作，操作共两种：交换操作：给定 xxx，将当前排列中的第 xxx 个数与第 x+1x+1x+1 个数交换位置。询问操作：给定 kkk...

Description\huge{\texttt{Description}} Description 1.O(n!)O(n!)O(n!) 想法首先，N≤8N\le 8N≤8，所以说标准做法就是一个一个枚举。你当然可以用 C++ 的 ST...