动态规划 - Page 7

「JoyOI」五月有奖赛暨Loi 55 Round #1 Day1
题解http://pan.baidu.com/s/1bnjO0ij选择题（byDarkfalmes）[crayon-67435c512644c883387113/]王的对决！(byrainheart&seavot)[crayon-67435c5126457071361934/]dC的肥皂（byskyfall（Orz））60暴力[crayon-67435c512645e337262047/]DQS和序列（by帝江&Darkfalmes）[crayon-67435c5126465318913325/] ...
22015年4月30日4,025递推与动规,线段树,筛法,广度搜索,莫比乌斯反演

「BZOJ4027」[HEOI2015] 兔子与樱花
Description很久很久之前，森林里住着一群兔子。有一天，兔子们突然决定要去看樱花。兔子们所在森林里的樱花树很特殊。樱花树由n个树枝分叉点组成，编号从0到n-1，这n个分叉点由n-1个树枝连接，我们可以把它看成一个有根树结构，其中0号节点是根节点。这个树的每个节点上都会有一些樱花，其中第i个节点有c_i朵樱花。樱花树的每一个节点都有最大的载重m，对于每一个节点i，它的儿子节点的个数和i节点上樱花个数之和不能超过m，即so...
02015年4月27日7,011贪心,树形动规
「BZOJ4008」[HNOI2015] 亚瑟王
Description小K不慎被LL邪教洗脑了，洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定，在脱坑之前，最后再来打一盘亚瑟王。既然是最后一战，就一定要打得漂亮。众所周知，亚瑟王是一个看脸的游戏，技能的发动都是看概率的。作为一个非洲人，同时作为一个前OIer，小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码，连Spaly都敲不对了，因此，希望你能帮帮小K，让他感受一下当欧洲人是怎样的体验。本题中我...
12015年4月22日7,466递推与动规,概率与期望
「BZOJ3997」[TJOI2015] 组合数学
Description 给出一个网格图，其中某些格子有财宝，每次从左上角出发，只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形，假设每个格子中有好多财宝，而每一次经过一个格子至多只能捡走一块财宝，至少走多少次才能把财宝全部捡完。Input 第一行为正整数T，代表数据组数。每组数据第一行为正整数N，M代表网格图有N行M列，接下来N行每行M个非负整数，表示此格子中财宝数量，0代表没有Output 输出一个整数...
22015年4月22日5,071递推与动规
「BZOJ3572」[HNOI2014] 世界树
Description 世界树是一棵无比巨大的树，它伸出的枝干构成了整个世界。在这里，生存着各种各样的种族和生灵，他们共同信奉着绝对公正公平的女神艾莉森，在他们的信条里，公平是使世界树能够生生不息、持续运转的根本基石。世界树的形态可以用一个数学模型来描述：世界树中有n个种族，种族的编号分别从1到n，分别生活在编号为1到n的聚居地上，种族的编号与其聚居地的编号相同。有的聚居地之间有双向的道路相连，道路的长度为1。保...
22015年4月21日11,009虚树,树形动规
「BZOJ3573」[HNOI2014] 米特运输
Description米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通道连接起来，构成一棵以1号城市（首部）为根的树，高速通道的方向由树中的儿子指向父亲。树按深度分层：根结点深度为0，属于第1层；根结点的子节点深度为1，属于第2层；依此类推，深度为i的结点...
02015年4月21日4,181树形动规
「BZOJ3675」[Apio2014] 序列分割
Description小H最近迷上了一个分割序列的游戏。在这个游戏里，小H需要将一个长度为N的非负整数序列分割成k+l个非空的子序列。为了得到k+l个子序列，小H将重复进行七次以下的步骤：1．小H首先选择一个长度超过1的序列（一开始小H只有一个长度为n的序列一一也就是一开始得到的整个序列）；2．选择一个位置，并通过这个位置将这个序列分割成连续的两个非空的新序列。每次进行上述步骤之后，小H将会得到一定的分数。这个分数为...
42015年4月19日8,413斜率优化,决策单调性
「East!_XX」手机号码
Description众所周知，天朝泱泱五千年的文化积淀下，人们在数字上尤为挑剔。很多人认为，不吉利的数字会导致流年困顿。「阿弥陀佛，作为社会主义接班人，我们应该相信科学，远离迷信!」在天朝，不同的人读手机号码有不同的方式（见右图）。人们选择手机号码时，为了照顾“不吉利数字恐惧症”患者，总会希望任何人报自己的电话号码时都不会连续说出来不吉利数字。例如，很多天朝子民认为5914是一串很不吉利的号码，因此尾号为5914的...
02015年4月18日2,622递推与动规
UOJ Round #1
http://vfleaking.blog.uoj.ac/blog/33「UR#1」缩进优化[crayon-67435c5128f31121828481/]「UR#1」外星人这题似乎没那么麻烦f[i][j]表示前i大的，得出的结果为j的方案数第i大的可以在当前视之生效，也可以放在剩下n-i个任意一个的后面使之不生效[crayon-67435c5128f3b928818614/]「UR#1」跳蚤国王下江南什么。。仙人掌毁灭世界。？这个大坑估计不会填了...
32015年4月14日4,066递推与动规,调和级数
「CF534X」Codeforces Round #298 (Div. 2)
「cf534A」Examyy个奇怪的构造TT[crayon-67435c512982b996256002/]「cf534B」CoveredPathd很小，最大速度就很小，dp即可[crayon-67435c5129834221679189/]「cf534C」Polycarpus'Dice对于每个骰子，得出其它骰子的和sum则它的最小值为A-sum，最大值为A-n+1[crayon-67435c512983a380246311/]「cf534D」Handshakes尽量大的能处理则处理[crayon-67435c512983e463113490/]「cf534E」BerlandLocalPositioningSystem非...
02015年4月13日3,486递推与动规,贪心,构造,深度搜索,状压动规
「codechef」April Challenge 2015
BROKPHON模拟[crayon-67435c5129e45911772662/]CHEFLCM所有约数和[crayon-67435c5129e4f783713966/]PIANO1暴力TT[crayon-67435c5129e53707606207/]CSEQl~r之间每个数的使用次数当作一个变量。。那么就相当于求方程组sigma(xi)(l<=i<=r)=n的非负整数解数。。然后就是排列组合求和[crayon-67435c5129e57015844312/]CARLOS先用并查集将能够相互转化的并在一起dpf(i,j)表示前i个末尾为j的最小改...
22015年4月12日4,882递推与动规,模拟,ST表,并查集,排列组合,乘法逆元
「BZOJ1912」[Apio2010] patrol 巡逻
DescriptionInput第一行包含两个整数n,K(1≤K≤2)。接下来n–1行，每行两个整数a,b，表示村庄a与b之间有一条道路(1≤a,b≤n)。Output输出一个整数，表示新建了K条道路后能达到的最小巡逻距离。SampleInput8112313453758556SampleOutput11HINT10%的数据中，n≤1000,K=1；30%的数据中，K=1；80%的数据中，每个村庄相邻的村庄数不超过25；90%的数据中，每个村庄相邻的村庄数不超过150；100%的数据中，3≤n≤100,000,1...
02015年4月9日4,799树形动规