wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共40篇）

[codevs3342][绿色通道]

codevs3342 思路：既然是要求最小化最长空题段，直接二分答案。然后就是check函数的写法。先考虑n方转移，假设当前二分的答案是x，用f[i]表示前i个题，第i道题写的最小花费时间。最后再去判断后f数组的后x个值是否小于等于要求时间的。然后返回。 int check(int x)...

动态规划dp 单调队列

2018-10-07

0 383

[bzoj4709][柠檬]

bzoj4709 思路首先，最优秀的分法一定是每段两端都是这一段中最多的那个，否则可以把不是的那个踢出去单独成段肯定会更优秀。然后就成了将这个序列分段，保证每段两端元素相同的最大收益和。用a[i]记录第i个位置上的数，用s[i]记录前i个元素中a[i]出现的次数。f[i]表示以前i个数的最...

动态规划dp 决策单调性

2018-10-08

0 348

[hdu6148][Valley Numer]

hdu6148 思路一个数位dp模板题，注意判断前导0。用一个bz来记录当前是应该增还是可增可减。然后排除不满足条件的情况并进行dp即可。代码 #include<cstdio> #include<iostream> #include<cstring> ...

动态规划dp 数位dp 位运算

2018-10-09

0 396

[luogu2657][windy数]

luogu2657 思路数位dp，记录下上个位置的数，如果当前的数字与上个数字的差值小于2，就不再转移。还是要注意排除前导0。在记忆化的时候，全都是前导0的情况不能记忆化。代码 #include<cstdio> #include<iostream> #includ...

数位dp 动态规划dp

2018-10-10

0 406

bzoj3900 交换茸角

题目链接思路看到n比较小，可以状压。可以先考虑什么情况下会无法平衡。显然就是排完序之后两两相邻的不能满足小于等于c的限制。状态。用f[i]来表示i集合中的鹿完成交换所需要的次数。预处理。无法平衡的肯定就是INF。已经平衡的是0。其他的先暂设为k-1(k是i集合中鹿的个数)。然后转移。...

动态规划dp 状态压缩

2019-01-24

0 472

bzoj2448 挖油

题目链接题面思路先考虑\(n \leq 100\)的做法。区间dp。状态。用\(f[l][r]\)表示知道l到r内\(x\)的位置最少需要的时间转移。枚举一个\(l \leq k \leq r\)。那么现在我们要在k处挖油了，然后我们根据k处有没有油再去确定下次是挖\([k +...

动态规划dp 单调队列

2019-01-24

0 504

bzoj2086 Blocks

题目链接题面思路可以发现其实就是询问一个最长的区间，使得这个区间的平均数大于等于k。所以将区间内所有数字减去k，然后做一遍前缀和。只要是前缀和之差大于等于0的区间。就是满足条件的。所以现在问题就成了对于前缀和上的每个数字，找到一个最靠前的比他小的数字。这个可以用单调栈。可以发现如...

动态规划dp 单调栈

2019-01-24

0 420

hihocoder1364 奖券兑换

题目链接思路乍一看这是一个01背包的裸题。但是数据范围\(10^5\)是无法承受的。但是发现\(p_i\)和\(w_i\)只有10，也就是说最多只有100种物品。所以可以对他们进行分组。然后用二进制优化多重背包来做。二进制优化多重背包多重背包是指限定物品数量的一种背包问题。多重背...

动态规划dp 背包

2019-01-24

0 493

hdu4899 Hero meet devil

题目链接题意给出一个长度字符串\(T\)，其中只包含四种字符\((A,C,G,T)\),需要找一个字符串\(S\)，使得\(S\)的长度为\(m\)，问\(S\)和\(T\)的\(lcs\)为\(0,1,2...|T|\)时，分别有多少种情况。 \(|T| <= 15,m <= ...

动态规划dp 状态压缩 dp套dp

2019-01-24

0 574

bzoj1030 文本生成器

题目链接题意给出\(n\)个字符串，要构造一个长度为\(m\)的字符串\(S\)，使得给出的\(n\)个字符串中至少有一个是\(S\)的子串。问方案数。思路 \(AC\)自动机+\(DP\) 考虑至少有一个是S的子串不好考虑。考虑用全部情况减去其中不包含任何一个字符串的情况。全部情况...

AC自动机动态规划dp

2019-02-01

0 564