冒泡ioa
冒泡ioa

动态规划
文章归档

[JXOI2017]数列(动态规划)

题面链接 题解 题目意思有点不好懂,其实就是在数列中找到与 $A_{i-1}$ 相邻的两项来限制 $A_i$ 的值,问方案数。 首先凭感觉,感觉越往后面的数可能的情况是更少的,整体呈收束趋势。 我们设用来更新 $A_i$ 的 $L$ 和 $R$ 为 $L_i$ 和 $R_i$ ,根据定义有 $L_{i-1…

   309   2019-05-09   去围观

[CF559C] Gerald and Giant Chess(动态规划)

题目链接 题解 先介绍一个东西:多重集(multiset)的全排列(这里是特殊情况,即选的元素个数不超过任意集合中元素个数的情况) 我们定义集合的集合为多重集,比如我有 $a_1$ 个 $1$ , $a_2$ 个 $2$ …… $a_n$ 个 $n$ 。 那么写成多重集就是 \(\left\{\left\{a_1·1\r…

   331   2019-05-06   去围观

[CF611D]New Year and Ancient Prophecy(动态规划)

题目链接 题解 $f[i][j]$ 表示 当前串为第j个位置到第i个位置的串的方案数 $O(n^3)$ 做法 $ f[i][j]=\sum_{j-k< i-j}f[j][k]$ 若 $s(k+1,j)< s(j+1,i),j-k=i-j$ 则 $f[i][j]+=f[j][k]$ $O(n^2)$ 做法 考虑 $O(1)$ check $s(k+1,j)<s(j+1,i)$ 逗逼神仙…

   294   2019-04-06   去围观

[Day6]B 君的第三题 (shenyang)

题目大意 给你一个长度为n的数组,你需要更改里面各项的值使得它们两两互质。 代价为改后数字与原始值的差值的绝对值。求最小代价。 题解 这个题解算是在分享做题的心路历程,比较磨叽,可以只看黑体字部分 一开始都已经弃疗了(别一开始就放弃啊喂!)准备打一…

   298   2019-01-30   去围观

【考前冲刺Day6】OI STILE

T1 引子(水箱) 非常简单的模拟题目,错误点有两处: 1. 没有读入多位数字 2. 出现顺序和编号无关 然就是从1号水箱,开始递归,优先从箱底的水管递归下去,然后输出自身的编号。 [crayon-6104018e022ba893688278/] T2 可爱精灵宝贝 一道区间dp题,考场上写挂了…

   361   2018-11-08   去围观

11.2 DP专题——和DP打成一片题解

T1 求三角形的最大面积 题目大意:给你一个由多个三角形组成的大三角形,其中有些三角形缺失了,求出剩下部分最大的三角形。 毒瘤题,dp很好想,被特殊情况坑了。 首先上三角和下三角都要算一遍(其实就是反过来再找一遍) 就拿上三角来说,我们很容易就知道它的…

   355   2018-11-02   去围观

11.1不能与DP好好相处题解

T1 不老的传说 题目大意:有n个石头环成一圈,每次染色能染1-k个连续石头,问多最少多少次能染成目标状态 这道题真的是各种既视感,环的话直接变成两倍的链就OK了,之后就是区间dp \(f[i][j]\)表示(i,j)对i,j一段染色的最少次数 初始化就是\(f[i][j]=\begin{cas…

   295   2018-11-01   去围观

[水题]终极简单问题

题目大意:两个人玩牌,他们各有m(<=100)张牌,输入牌上的数字(<=50),有n(<=50)轮回合,每回合他们从自己牌中随机选1张,牌上的数字加入答案后放回牌组中。问n回合后第一个人赢的概率是多少(保留6位小数)? 我当时居然还想随机模拟最后输出答案(显然精…

   771   2018-10-30   去围观

[水题]w

题目大意:有一棵 n 个节点的树,每条边长度为 1,颜色为黑或白。 可以执行若干次如下操作:选择一条简单路径,反转路径上所有边的颜色。 对于某些边,要求在操作结束时为某一种颜色。 给定每条边的初始颜色,求最小操作数,以及满足操作数最小时,最小的操作路…

   341   2018-10-29   去围观

[LOJ10181]绿色通道

传送门 一看到求什么“最大的最小值”,“最小的最大值”就马上想到二分(还有可能是单调队列) 再仔细看看题目,貌似没什么头绪,但答案似乎存在单调性,果断二分。 答案肯定在0到n范围内。 设\(f[i]\)为做到第\(i\)个作业时所需要花的最短时间。 假如我们可以空\(k\)道…

   469   2018-10-07   去围观
加载更多