RainAir
My OI Blog
RainAir

动态规划
文章归档

「CF840C」On the Bench

题目大意 给你一个长度为 $n$ 的序列,问你有多少种置换,使得置换后的序列相邻两项的乘积都不是平方数。 题解 这个题目好像比较厉害的样子。。首先把这些数按照是否能组成平方数分组,同一组里都是两两相乘能凑成平方数的,可以证明存在这样的分配方案。 然后我们…

   64   2019-08-28 去围观

轮廓线 dp 学习笔记

轮廓线 dp 也是一种状压,适用于一维特别大而另一维特别小的情况。 我们来从一道经典例题入手:求 $1 \times 2$ 的骨牌填满 $n \times m $ 的矩形的方案数。 如果 $n,m \leq 11$ 那么当然可以轻松状压了,但是如果 $n = 10^5$ ,我们就要考虑使用轮廓线 dp 了。 设 $f_…

   84   2019-08-26 去围观

「CF833B」The Bakery

题目大意 把 $n$ 个数分成 $k$ 个区间,每个区间的价值为区间内不同数字的个数,问价值和最大为多少。 题解 简单 dp:设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量,那么有转移 $$f_{i,j} = …

   152   2019-08-26 去围观

DDP 学习笔记

DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场上根本不会...那个时候我是连暴力 dp 都不会的菜鸡,现在回来学一学。 我们来找一…

   167   2019-07-11 去围观

ZROI466小 G 的数

最近从某个地方看到了这个题。。。所以回来补一下题解。 题目描述 题解 直接求期望不太好求,我们可以考虑求出每一种条件下的概率,最后乘上直径长度就可以了。 我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里,目前不跨过 $i$ 节点的最长链是 $j$,子树的直径是…

   139   2019-07-08 去围观

「NOI2005」瑰丽华尔兹

题目链接 题目大意 现在有一个 $n\times m$ 的矩阵,给定的起始点上有个钢琴,矩阵上有些方格是障碍物,用连续的区间 $[l,r]$ 和一个参数 $d$ 表示在时间 $[l,r]$ 时会向 $d$ 方向滑动(上下左右),当然每个时间点可以选择让钢琴不动,不允许钢琴超出边界或者碰到障…

   96   2019-07-07 去围观

HDU 3480 Division

题目链接 题意 有长度为 n 的序列,定义一个集合的代价是$(MAX-MIN)^2$,要求你找出 m 个集合,在满足下面图片的限制的情况下,使得总代价最小。 多组数据,每组数据 $n \leq 10^4,m \leq 5 \times 10^3$,保证答案在 int 范围内。 题解 观察题目 发现让你选取 M …

   95   2019-07-06 去围观

「BZOJ2553」「BJOI2011」禁忌

题目链接 题目描述 题目大意:给你前 $alphabet$ 个小写字母组成的字符集,以及 $n$ 个单词,定义一个串 s 的禁忌值为 $\sum_{i} [s[i] == Taboo[i]]$,其中 $Taboo[i]$ 是第 $i$ 个单词(禁忌值也就是找到一种分割字符串的方法 使得出现这N个字符串的次数最多的次数…

   220   2019-05-01 去围观

「CF623E」 Transforming Sequence

题目链接 没想到非 Chinese Round 也会出这么毒瘤的题目...... 题目大意:对于正整数序列 $A$,定义序列 $B$: $B_1=A_1,B_i=B_{i-1}\ or\ A_i,i\in[2,n]B $ 其中 or 为位或运算。 每一个序列合法,满足对于$ \forall i\in[1,n]$,有 $A_i\in[1,2^k])$ 而且对于 $\fo…

   270   2019-03-14 去围观

密码保护:「19省选1」题解

这篇文章受密码保护,输入密码才能看哦

   390   2018-12-05 去围观
加载更多
标签
近期评论