文档章节

Codeforces - tag::dp 大合集 [占坑 6 / inf]

o
 osc_odyg6b92
发布于 2018/07/13 16:20
字数 1411
阅读 15
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

Gym - 100753J

某国家仅有金币和银币两种货币,起汇率为g,纪念品市场有n个商人和商品,商人结帐只用银币,并且把一堆银币装在袋子里,分为三种类型,分别按向下/向上/四舍五入取整(其中向上的优先使用银币交易),你要用c个金币买尽量多纪念品,输出最多纪念品数

细节较多的二维背包水题,差点没把我气死

注意不要把第三维改成纪念品数而答案为最多保留的银币数

不然无法处理generous的情况

https://paste.ubuntu.com/p/WNCSWc9rfs/


407B

要求从节点1走到节点n+1,每个节点有2个出口,当奇数次经过$i$时走到$p_i,p_i≤i$节点,偶数次经过时走到$i+1$节点,求走过的步数模1e9+7

设1到i+1的步数:$dp[i+1]=dp[i]+1+dp[i]-dp[p[i]]+1$(对于i分为奇偶两次遍历) 设到i+1的步数:$dp[i]=1+dp[p[i]]+dp[p[i]+1]+...+dp[i-1]+1$(到达i+1时,对于1...i都是偶数步) 设$dp[i][j]:$ $i$到$j$的步数:$dp[i][j]=dp[i][j-1]+dp[p[j-1]][j-1]+1$(对于j-1,i到j-1为奇数步,p[j-1]到j-1位偶数步) 注意p[i]可等于i因此i=j时也算1步


5C

求最长的括号匹配和对应的个数

栈+DP

$l$为当前匹配下标,$dp$为最早匹配下标

https://paste.ubuntu.com/p/xJY6FBgy9h/


340D

给定一个序列,对其进行冒泡排序,每次交换都会两个元素连边形成冒泡排序图,求该图中的最大点独立集

看不出来orz,%了题解后感觉十分不可思议orz

https://www.cnblogs.com/hehe54321/p/cf-340d.html


814C

给定一个长度1k5的串,2e5次询问最多修改k个数求字符ch的最大连续区间

设$dp[i][j][k]$:从$i$到$j$把字符全部变为$k$的最小代价

记$ans[i][k]$:最多修改$i$次的最长连续$k$字符区间的递推答案,注意是最多,不是exactly

那么可以在$O(26n^3)$以内完成预处理

https://paste.ubuntu.com/p/mVFPtfBCzs/


607B

给定一个数组a[1...n],每次操作可消除一个回文子串,求最少操作次数使得原串被消除

区间dp

https://paste.ubuntu.com/p/KvhRwWZCGG/


660C

(然而这是一道二分题目)

题意:给定$a[1...n]$的01串,至多可以使k个0变为1,求最长的连续全1串的长度及方案

维护sum[i]:前i项中0的个数

那么每次可以通过sum的单调性二分出最远的可连续更改位置

注意判断条件

https://paste.ubuntu.com/p/R92nXsk9Hv/


812B(水)

题意:n层楼每层m个房间2个楼梯,每一层关灯后才可以上再高一层,问灯全关的最少步数

对楼梯记录来自下层哪个楼梯的最优代价即可,有点细节(WA了你就知道了

https://paste.ubuntu.com/p/2ThySDZF62/


766C

题意:给出一个串和每个字符允许存在的最多次数,求分割合法子串方案数/可能的最长子串长度/可能的最少的子串数

枚举分割的子串既要求每个字符满足a[str[x]-'a']<=i-j+1

方案数只需加上之前分割出的段的方案数

https://paste.ubuntu.com/p/k2GscFnfzC/


270D

题意:n个实数点m个种类,求最少移动多少个点使得m-1个隔板中间都是同一种类并且种类是升序的

最多不移动的点就是LIS

n-LIS就是所求


505C

节省空间


557C


629C

题意:定义合法串,串中只有a和b,前缀和满足$prea_i≥preb_i$,且最后一位$prea=preb$,现在给定了长为m的串,要求构造出p+q,使p+s+q为合法串,求构造的方案数,n≤100000,n-m≤2000

定义$dp[i][j]$:前$i$位$prea_i-preb_i=j$的方案数,转移方程为$dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]$

此时$dp[i][-j]=dp[i][j]$

预处理出n-m的所有方案 对于p串,设包含$prea',preb'$要求随时满足$prea'+prea-preb'-preb≥0$,既$prea'-preb'≥min(prea_i-preb_i)$ 在满足p+q在任意位置均合法的情况下,对于q串,设包含$prea'',preb''$,要求满足$prea'+prea+prea''-preb'-preb-preb''=0$,既$prea''-preb''=prea-preb+prea'-preb'$ 注意枚举时长度的限制

https://paste.ubuntu.com/p/fPRybn45S2/


ZOJ - 4027(乱入)

待做/不想做:1005D/219C/798C/919D


probabilities

839C

题意:求从一棵树的根随机跑到叶子的期望长度

对叶子设$dp[u]=0$,其余部分$dp[u]=1+\sum dp[v]/cnt$


453A

题意: 有一个m面均匀骰子,求抛n次的最大面的期望数值

每次抛都是独立的,可看作n个骰子(然并卵),对于n个骰子单次抛出最大面为1的概率$\frac{1}{m^n}$,最大面为2的概率为$(\frac{2}{m})^n-(\frac{1}{m})^n$,最大面为$i$的概率为$(\frac{i}{m})^n-(\frac{i-1}{m})^n$,每次乘上$i$便得到期望


312B

题意:Alice和Bob在玩游戏,Alice的单次胜率为$a/b$,Bob的位$c/d$,Alice先手,求Alice获胜的概率

第一次获胜 $a/b$ 第三次获胜 $(1-a/b)(1-c/d)a/b$ 第五次获胜 $(1-a/b)(1-c/d)(1-a/b)(1-c/d)a/c=[(1-a/b)(1-c/d)]^2a/b$ 令$p=a/b,q=(1-a/b)(1-c/d)$,答案为$p\sum_{i=0}^{∞} q^i=p(1/(1-q))$

o
粉丝 1
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Python开发者社区整站源码--Pythoner

pythoner.net 整站源代码 依赖模块 Django 1.4.2 PIL DjangoVerifyCode 0.2.2 开发环境配置 运行scripts目录下的setupenv.sh文件,将会自动安装配置所需环境 设置本地环境变量:export env=D...

~T.y~
2013/04/10
3.1K
0
Redis 分片实现--Redis Shard

redis-shard 是 Redis 分区的 Python API ,基于对 key 和 key tag 进行 CRC32 checksum 计算,可参考文章 http://antirez.com/post/redis-presharding.html . 该项目由知乎网开发。 使用限制...

匿名
2012/10/24
5.6K
0
半同步/半异步的Tcp Server--LightningServer

这是一个半同步/半异步的Tcp Server. 支持以下特性: 1.使用了libevent库,支持大并发网络请求; 2.网络操作与数据处理分离; 3.使用线程池进行数据处理; 4.目前支持tcp数据流的解包操作: 4....

扫帚的影子
2012/12/24
2.7K
0
Alfresco Explorer客户化定制配置

有几种不同的方法定制Explorer配置选项,Explorer 配置文件是web-client-config-custom.xml   一、在目录修改 Explorer配置文件   1、打开 web-client-config-custom.xml 文件。   2、...

liubang
2012/07/19
831
0
微信框架的几个层次

第一层次:通信处理 对访问微信服务器进行处理,主要解决报文来来去去的问题。这里采用的技术一般是HttpClient或类似的技术。 第二层次:报文解析 通过对报文进行解析,让程序员直接要拿到的...

悠悠然然
2015/12/01
9.3K
58

没有更多内容

加载失败,请刷新页面

加载更多

如何在SQL Server中将多行文本合并为单个文本字符串?

问题: Consider a database table holding names, with three rows: 考虑一个包含名称的数据库表,该表具有三行: PeterPaulMary Is there an easy way to turn this into a single str......

富含淀粉
33分钟前
9
0
在JavaScript中生成特定范围内的随机整数? - Generating random whole numbers in JavaScript in a specific range?

问题: 如何可以生成两个指定的变量之间的随机整数在JavaScript中,例如x = 4和y = 8将输出任何的4, 5, 6, 7, 8 ? 解决方案: 参考一: https://stackoom.com/question/6PRz/在JavaScript中...

fyin1314
今天
8
0
Vim清除最后一个搜索突出显示 - Vim clear last search highlighting

问题: Want to improve this post? 想要改善这篇文章吗? Provide detailed answers to this question, including citations and an explanation of why your answer is correct. 提供此问题......

技术盛宴
今天
23
0
马化腾每天刷 Leetcode?代码你打算写到几岁?

本文作者:o****0 前几天,一张未证真伪的截图流传,图中显示马化腾几乎每天都会在 Leetcode 上提交代码。 截图还贴出一个 Leetcode 账户地址。该地址的头像已从马化腾的照片换成腾讯 logo,...

百度开发者中心
前天
13
0
滴滴 3000+ Kylin Cube 背后的实践经验揭秘

本次分享主要有三个部分:Kylin 在滴滴的整体应用、架构的实践经验、滴滴全局字典最新版本的实现以及 Kylin 最新实时 OLAP 探索经验分享。 Kylin 在滴滴的应用&架构 Kylin 在滴滴的三类应用场...

浪尖聊大数据
昨天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部