• 2024-07-17P5999 [CEOI2016] kangaroo的TJ
    [CEOI2016]kangaroo其实就是给你一个\(p_1,p_n\)确定,其余未知的排列,求有多少个合法的排列,满足一个数要么比他相邻的两边都大,要么比他相邻的两边都小。我们若是依次考虑每\(p_{1,2,\cdots,n}\),由于他的取值还和后面有关,我们不好考虑,考虑依次将\(i=1,2,\cdots,n\)填入当前的序列
  • 2024-05-19P5999 [CEOI2016] kangaroo
    题目大意求出有多少种排列\(p\)满足对于任意\(i\in(1,n)\)有\(p_i\)两侧的值同时大于或小于\(p_i\)。规定\(p_1=s,p_n=t\)。\(2\leqn\leq2\times10^3,1\leqs,t\leqn\)思路首先能看出是动态规划。但是如果纯区间动规的话不太好转移,因为无法使得两个区间拼接的部分
  • 2023-06-13P5999 [CEOI2016] kangaroo
    前言写这篇题解的原因是这道题提供了一种新的dp思路——插入dp。题意给定一个长为\(n\)的数轴,一只袋鼠在上面要从\(s\)跳到\(t\),跳跃过程中,每次跳跃方向必须与上一次相反,求方案数。分析拿到这个题其实还是蛮蒙的,但是如果我们转化(抽象)一下题意,就会发现这道题可以看作:
  • 2023-01-09P5999 [CEOI2016] kangaroo 题解
    分析一个妙妙的trick。首先原题可以转化成求有多少\(1\simn\)的排列\(p\)满足\(\foralli\in(1,n)\),\(p_i\)两边的数同时小于或大于\(p_i\),且\(p_1=s,p_n=t\)
  • 2022-11-18P5999 [CEOI2016] kangaroo 蓝 题解
    前言有些题目照常DP不是很好做,感觉像是区间DP,但是怎么设状态都不好转移,那么可以考虑一种维护块儿的DP,就是这道题要用到的知识点。背景分析如果每次跳跃的点的编号形
  • 2022-09-07P5999 [CEOI2016] kangaroo 题解
    感觉这样的\(\text{dp}\)题还比较多,思路都比较的神奇。个人感觉比较像区间\(\text{dp}\)的一类变种。但又和区间\(\text{dp}\)的维护方式极不一样。对于此类\(\t