动态规划 - Page 12

「BZOJ3174」[TJOI2013] 拯救小矮人
Description一群小矮人掉进了一个很深的陷阱里，由于太矮爬不上来，于是他们决定搭一个人梯。即：一个小矮人站在另一小矮人的肩膀上，知道最顶端的小矮人伸直胳膊可以碰到陷阱口。对于每一个小矮人，我们知道他从脚到肩膀的高度Ai，并且他的胳膊长度为Bi。陷阱深度为H。如果我们利用矮人1，矮人2，矮人3,。。。矮人k搭一个梯子，满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了，一旦一个矮人逃跑了，他就...
02014年12月9日3,637递推与动规

「BZOJ3770」疯狂的限制
Description给定k个限制条件，其中第i个条件用c[i],l[i],r[i]表示：字符c[i]在字符串中的出现次数大等于l[i]，小等于r[i]。若一个字符串满足的限制条件的个数大等于L，小等于R，则称该串为StenisString给定一小写字母串s，求s有多少个子串是SteinsString。Input第一行一个非空的小写字母串s第二行三个整数k,L,R。以下k行，每行1个字符和2个整数表示c[i],l[i],r[i]Output一个整数，表示答案SampleInputelpsycongroo312...
42014年12月8日3,092递推与动规
「BZOJ3769」「SPOJ 8549 BST again
Description求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）Input第一行一个整数T，表示数据组数。以下T行，每行2个整数n和h。Output共T行，每行一个整数表示答案（对1000000007取模）SampleInput22132SampleOutput24HINT对于100%的数据，1<=n<=600,0<=h<=600,1<=T<=10题解f[i][j]表示大小i，深度小于j的二叉树数量则f[i][j]=(1<=k<=i)Σf[k-1]...
02014年12月3日2,903递推与动规
「BZOJ2298」[HAOI2011] problem a
Description一次考试共有n个人参加，第i个人说：“有ai个人分数比我高，bi个人分数比我低。”问最少有几个人没有说真话(可能有相同的分数)Input第一行一个整数n，接下来n行每行两个整数，第i+1行的两个整数分别代表ai、biOutput一个整数，表示最少有几个人说谎SampleInput3200222SampleOutput1题解100%的数据满足：1≤n≤100000 0≤ai、bi≤n求最多说真话的人数，答案即为n-ans设dp[i]表示在前i名中最多有多少人说真话dp...
32014年12月1日5,465递推与动规
「BZOJ1055」[HAOI2008] 玩具取名
Description某人有一套玩具，并想法给玩具命名。首先他选择WING四个字母中的任意一个字母作为玩具的基本名字。然后他会根据自己的喜好，将名字中任意一个字母用“WING”中任意两个字母代替，使得自己的名字能够扩充得很长。现在，他想请你猜猜某一个很长的名字，最初可能是由哪几个字母变形过来的。Input第一行四个整数W、I、N、G。表示每一个字母能由几种两个字母所替代。接下来W行，每行两个字母,表示W可以用这两...
12014年12月1日5,791区间动规,记忆化搜索
「BZOJ1048」[HAOI2007] 分割矩阵
Description将一个a*b的数字矩阵进行如下分割：将原矩阵沿某一条直线分割成两个矩阵，再将生成的两个矩阵继续如此分割（当然也可以只分割其中的一个），这样分割了（n-1)次后，原矩阵被分割成了n个矩阵。（每次分割都只能沿着数字间的缝隙进行）原矩阵中每一位置上有一个分值，一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成n个矩阵，并使各矩阵总分的均方差最小。请编程对给出的矩阵及n，求出均方差的...
02014年12月1日5,192记忆化搜索
「BZOJ1049」[HAOI2006] 数字序列
Description现在我们有一个长度为n的整数序列A。但是它太不好看了，于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数，也不希望改变的幅度太大。Input第一行包含一个数n，接下来n个整数按顺序描述每一项的键值。Output第一行一个整数表示最少需要改变多少个数。第二行一个整数，表示在改变的数最少的情况下，每个数改变的绝对值之和的最小值。SampleInput45235SampleOutput14HINT「数据范围」90%的...
12014年12月1日5,649递推与动规
「BZOJ1060」[ZJOI2007] 时态同步
Description小Q在电子工艺实习课上学习焊接电路板。一块电路板由若干个元件组成，我们不妨称之为节点，并将其用数字1,2,3….进行标号。电路板的各个节点由若干不相交的导线相连接，且对于电路板的任何两个节点，都存在且仅存在一条通路（通路指连接两个元件的导线序列）。在电路板上存在一个特殊的元件称为“激发器”。当激发器工作后，产生一个激励电流，通过导线传向每一个它所连接的节点。而中间节点接收到激励电流后，得到信...
22014年11月30日4,851树形动规
「BZOJ1042」[HAOI2008] 硬币购物
Description硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。Input第一行c1,c2,c3,c4,tot下面tot行d1,d2,d3,d4,sOutput每次的方法数SampleInput1251023231101000222900SampleOutput427HINT数据规模di,s<=100000tot<=1000题解我想起了cf的某道题。。。dp预处理+容斥原理byvoid：设F[i]为不考虑每种硬币的数量限制的...
32014年11月30日8,862递推与动规,容斥原理
「BZOJ2216」[POI2011] Lightning Conductor
Description已知一个长度为n的序列a1,a2,...,an。对于每个1<=i<=n，找到最小的非负整数p满足对于任意的j,aj<=ai+p-sqrt(abs(i-j))Input第一行n，(1<=n<=500000)下面每行一个整数，其中第i行是ai。(0<=ai<=1000000000)Outputn行，第i行表示对于i，得到的pSampleInput6532424SampleOutput235354题解倒腾一下式子得出f[i]=max{a[j]+sqrt(abs(i-j))}-a[i]为了把绝对值去掉就正反各做一次取最大值这个式子显...
52014年11月29日6,234决策单调性
NOI2009诗人小G
DescriptionInputOutput对于每组数据，若最小的不协调度不超过1018，则第一行一个数表示不协调度若最小的不协调度超过1018，则输出"Toohardtoarrange"(不包含引号)。每个输出后面加"--------------------"SampleInput4493brysj,hhrhl.yqqlm,gsycl.492brysj,hhrhl.yqqlm,gsycl.110056poet110046poetSampleOutput108--------------------32--------------------Toohardtoarrange--------------------1000000000000000000---...
02014年11月29日6,072递推与动规,贪心,决策单调性
「BZOJ3437」小P的牧场
Description 背景小P是个特么喜欢玩MC的孩纸。。。描述小P在MC里有n个牧场，自西向东呈一字形排列（自西向东用1…n编号），于是他就烦恼了：为了控制这n个牧场，他需要在某些牧场上面建立控制站，每个牧场上只能建立一个控制站，每个控制站控制的牧场是它所在的牧场一直到它西边第一个控制站的所有牧场（它西边第一个控制站所在的牧场不被控制）（如果它西边不存在控制站，那么它控制西边所有的牧场），每个牧场被控制都需...
22014年11月29日6,609递推与动规,斜率优化