动态规划 - Page 13

「BZOJ1010」[HNOI2008] 玩具装箱toy
DescriptionP教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第...
72014年11月28日25,558斜率优化,决策单调性

「BZOJ1017」[JSOI2008] 魔兽地图DotR
DescriptionDotR(DefenseoftheRobots)Allstars是一个风靡全球的魔兽地图，他的规则简单与同样流行的地图DotA(DefenseoftheAncients)Allstars。DotR里面的英雄只有一个属性——力量。他们需要购买装备来提升自己的力量值，每件装备都可以使佩戴它的英雄的力量值提高固定的点数，所以英雄的力量值等于它购买的所有装备的力量值之和。装备分为基本装备和高级装备两种。基本装备可以直接从商店里面用金币购买，而高级装备...
42014年11月23日7,314树形动规
「BZOJ3427」POI2013 Bytecomputer
DescriptionAsequenceofN integersI1,I2…Infromtheset{-1,0,1}isgiven.Thebytecomputerisadevicethatallowsthefollowingoperationonthesequence:incrementingI(i+1)byI(i)forany1<=I<=N.Thereisnolimitontherangeofintegersthebytecomputercanstore,i.e.,eachI(i)can(inprinciple)havearbitrarilysmallorlargevalue.Programthebytecomputersothatittransformstheinputsequenceintoanon-decreasingsequence(i...
02014年11月22日2,963递推与动规
NOIP2014联合权值
题目描述Description无向连通图G有n个点，n-1条边。点从1到n依次编号，编号为i的点的权值为Wi ，每条边的长度均为1。图上两点(u, v)的距离定义为u点到v点的最短距离。对于图G上的点对(u,v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？输入输出格式Input/output输入格式：输入文件名为link.in。第一行包含1个...
22014年11月22日7,251树形动规
「BZOJ1089」[SCOI2003] 严格n元树
Description如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为２的严格２元树有三个，如下图：给出n,d，编程数出深度为d的n元树数目。Input仅包含两个整数n,d(0 < n < = 32, 0 <= d <=16)Output仅包含一个数，即深度为d的n元树的数目。SampleInput「样例输入1」22「样例输入2」...
02014年11月14日5,156递推与动规,高精度
「BZOJ2734」[HNOI2012] 集合选数
Description《集合论与图论》这门课程有一道作业题，要求同学们求出{1,2,3,4,5}的所有满足以下条件的子集：若x在该子集中，则2x和3x不能在该子集中。同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数n≤100000，如何求出{1,2,...,n}的满足上述约束条件的子集的个数（只需输出对1,000,000,001取模的结果），现在这个问题就交给你了。Input 只有一行，其中有一个正整数n，30%的数据满足n≤20。O...
62014年11月13日6,567状压动规
「CF486D」Valid Sets
Asyouknow,anundirectedconnectedgraphwithnnodesandn - 1edgesiscalledatree.Youaregivenanintegerdandatreeconsistingofnnodes.Eachnodeihasavalueaiassociatedwithit.WecallasetSoftreenodesvalidiffollowingconditionsaresatisfied:Sisnon-empty.Sisconnected.Inotherwords,ifnodesuandvareinS,thenallnodeslyingonthesimplepathbetweenuandvshouldalsobepresentedinS..Yourtaskistocountthenumberofvalidsets.S...
02014年11月12日3,553树形动规
「NOIP模拟赛」篮球比赛1
Czhou为了提高机房里各种神牛的身体素质，决定在每次训练后举行篮球比赛。为了保持比赛公平，Czhou要将神牛们分成两队。首先神牛们赛前都要排成固定的队伍；然后Czhou将队伍分成一半（前一半和后一半队伍人数可以不等），再分别从两个队伍中选出一些人进行篮球比赛。为了保持公平性，Czhou要求第一个队伍参加比赛的神牛能力的XOR值等于第二个队伍参加比赛的神牛能力的and值。为了增加比赛趣味，每次比赛的参加神牛们不能...
02014年11月5日3,472递推与动规
「NOIP模拟赛」篮球比赛2
由于Czhou举行了众多NOIP模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当...
12014年11月5日4,880背包动规,深度搜索,状压动规
「NOIP模拟赛」序列问题
「题目描述」小H是个善于思考的学生，她正在思考一个有关序列的问题。她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。这两个集合要满足以下的条件：1.两个集合中的元素都为整数，且都在[1,n]里，即Si，Ti∈[1,n]。2.对于集合S中任意一个元素x，集合T中任意一个元素y，满足x<y。3.对于大小分别为p,q的集合S与T，满足 a[s1]xora[s2]xora[s3]...xora[sp]=a[t1]anda[t2]anda[t3]...anda[tq]....
02014年11月4日5,901递推与动规,深度搜索
「NOIP模拟赛」改造二叉树
「题目描述」小Y在学树论时看到了有关二叉树的介绍：在计算机科学中，二叉树是每个结点最多有两个子结点的有序树。通常子结点被称作“左孩子”和“右孩子”。二叉树被用作二叉搜索树和二叉堆。随后他又和他人讨论起了二叉搜索树。什么是二叉搜索树呢？二叉搜索树首先是一棵二叉树。设key[p]表示结点p上的数值。对于其中的每个结点p，若其存在左孩子lch，则key[p]>key[lch]；若其存在右孩子rch，则key[p]<key[rch]；注意，本...
12014年11月4日2,845递推与动规
「NOIP模拟赛」机房人民大团结
最近，机房出了一个不团结分子：Dr.Weissman。他经常欺骗同学们吃一种“教授糖豆”，使同学们神志不清，殴打他人，砸烂计算机，破坏机房团结。幸运地，一个和谐家认清了Dr.Weissman的本质。机房人民团结在一起，共同对抗Dr.Weissman及“教授糖豆”。同学们十分具有社会责任感：他们害怕“教授糖豆”流向社会，导致动乱。于是，刚才提到的和谐家身先士卒，为了实验，品尝“教授糖豆”。每个“教授糖豆”的性质都有所不同。同志...
02014年11月2日3,069递推与动规