动态规划 - Page 19

「CF451D」Count Good Substrings
Wecallastring good,ifaftermergingalltheconsecutiveequalcharacters,theresultingstringispalindrome.Forexample,"aabba"isgood,becauseafterthemergingstepitwillbecome"aba".Givenastring,youhavetofindtwovalues:thenumberofgoodsubstringsofevenlength;thenumberofgoodsubstringsofoddlength.InputThefirstlineoftheinputcontainsasinglestringoflength n (1 ≤ n ≤ 105).Eachcharacterofthestringwillbeeithe...
02014年7月25日2,568递推与动规

「BZOJ1633」[Usaco2007 Feb] The Cow Lexicon 牛的词典
Description没有几个人知道,奶牛有她们自己的字典,里面的有W(1≤W≤600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音.奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L(2≤L≤300)的字符串.有些时候,这个字符串...
02014年7月24日3,071递推与动规
「BZOJ1643」[Usaco2007 Oct] Bessie’s Secret Pasture 贝茜的秘密草坪
Description农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积为N(1<=N<=10,000)个单位面积的部分。贝茜对选出这样四块草皮的方法数...
02014年7月24日2,635递推与动规
「BZOJ1688」[Usaco2005 Open] Disease Manangement 疾病管理
DescriptionAlas!AsetofD(1<=D<=15)diseases(numbered1..D)isrunningthroughthefarm.FarmerJohnwouldliketomilkasmanyofhisN(1<=N<=1,000)cowsaspossible.IfthemilkedcowscarrymorethanK(1<=K<=D)differentdiseasesamongthem,thenthemilkwillbetoocontaminatedandwillhavetobediscardedinitsentirety.PleasehelpdeterminethelargestnumberofcowsFJcanmilkwithouthavingtodiscardthemilk.Input...
12014年7月23日3,830状压动规
「fj夏令营」营销策略
「题目描述」W记的儿童套餐会赠送一份小玩具，赠送的小玩具共有n种。小朋友买了m份儿童套餐，求收集齐n种小玩具的概率。假设每份儿童套餐赠送的小玩具的种类是等概率随机的。「输入格式」从pattern.in中输入数据一行，两个整数n，m。「输出格式」输出到pattern.out中一个实数表示收集齐小玩具的概率，保留4位小数。「样例输入」23「样例输出」0.7500「数据规模与约定」对于10%的数据保证：n=1对于30%的数据保证：n≤2对于60%的数据...
02014年7月20日3,986递推与动规,概率与期望
「czy系列赛」蒟蒻czy又被D飞了
（本题中的图片忽略）「题目描述」机房里的各路巨神天天D蒟蒻CZY，早已是他们的日常任务了。（今天的机房也是很和平呢）这一次他们安排好了一种方式来D蒟蒻Czy。每个人每次都能把CzyD飞一个高度（让Czy的高度+a[i]），由于他们的精♂力有限（尤其是某些后宫王），要保留体力应对接下来的战♂斗，所以他们每个人只会DCzyk[i]次。由于他们每个人的D人能力不同，各有所长，所以他们每个人都在Czy到一定高度h[i]以后良心发...
32014年7月19日3,932背包动规
「czy系列赛」czy的后宫6
czy的后宫6题目描述众所周知的是丧尸czy有很多妹子（虽然很多但是质量不容乐观QAQ），今天czy把n个妹子排成一行来检阅。但是czy的妹子的质量实在……所以czy看不下去了。检阅了第i个妹子会增加czya[i]的肾虚值，他打算在检阅过程中最多休息m次（一开始检阅算0次休息，就是说czy最多可以检阅m+1次），每次休息过后czy又会龙精虎猛的继续检阅。问怎样分配才能使得czy在检阅过程中的最大肾虚值最小。当然这么简单的问题czy早就会做...
02014年7月19日3,693递推与动规,二分法
「czy系列赛」czy的后宫5
czy的后宫5描述czy要召集他的妹子，但是由于条件有限，可能每个妹子不能都去，但每个妹子都有一个美丽值，czy希望来的妹子们的美丽值总和最大（虽然……）。czy有一个周密的电话通知网络，它其实就是一棵树，根结点为czy，他可以通知一些妹子（毕竟他不认识他的所有妹子嘛），称为他的下线（也就是儿子节点），下线们继续通知自己的下线。任何妹子都可以不去，但是任何一个妹子如果要去，则她的上线（也就是她的父亲节点）一定要去...
12014年7月19日5,378背包动规
「czy系列赛」czy的后宫4
「问题描述」czy有很多妹子，妹子虽然数量很多，但是质量不容乐观，她们的美丽值全部为负数（喜闻乐见）。czy每天都要带N个妹子到机房，她们都有一个独一无二的美丽值，美丽值为-1到-N之间的整数。他想要把这些妹子排成一个波动序列，这样相对“漂亮”（美丽值的绝对值较小）的妹子可以与她旁边的两个美丽值的绝对值较大的妹子形成鲜明的对比，整个序列相对将更加“美观”（不再那么无法直视）。一个序列是波动序列仅当序列中的每...
02014年7月19日3,208递推与动规
「BZOJ3688」「FJ2014集训」折线统计
「题目描述」二维平面上有n个点(xi,yi)，现在这些点中取若干点构成一个集合S，对它们按照x坐标排序，顺次连接，将会构成一些连续上升、下降的折线，设其数量为f(S)。如下图中，1->2,2->3,3->5,5->6（数字为下图中从左到右的点编号），将折线分为了4部分，每部分连续上升、下降。现给定k，求满足f(S)=k的S集合个数。「输入格式」第一行两个整数n和k，以下n行每行两个数(xi,yi)表示第i个点的坐标。所有点的坐标值都在...
02014年7月13日4,818递推与动规,树状数组
「FJ互测」「BZOJ3704」昊昊的机油之GRST
题目描述(grst.c/cpp/pas)昊昊有个好机油，他就是传说中的着力点。现在昊昊获得了一份长度为n的GRST牌（mod4意义下），打算作为送给好机油的生日礼物（不是在2月的么）。但是，昊昊深知他的机油是个神犇，作为数字控的他，只会喜欢特定的序列。但是昊昊不怕，他可以使用一次菲亚特（他的机油最喜欢的大招），将一段区间内的数字全部+1，若某个数字为3，则+1后变为0。但昊昊的神力是有限的，问从初始序列a到达最终序列b，最少需...
02014年7月12日3,714递推与动规,贪心
「BZOJ1806」[IOI2007] Miners 矿工配餐
Description现有两个煤矿，每个煤矿都雇用一组矿工。采煤工作很辛苦，所以矿工们需要良好饮食。每当一辆食品车到达煤矿时，矿工们便会产出一定数量的煤。有三种类型的食品车：肉车，鱼车和面包车。矿工们喜欢变化的食谱。如果提供的食品能够不断变化，他们的产煤量将会增加。每当一个新的食品车到达煤矿时，矿工们就会比较这种新的食品和前两次（或者少于两次，如果前面运送食品的次数不足两次）的食品，并且：•如果这几次食品车...
02014年7月10日4,090递推与动规