动态规划 - Page 17

「BZOJ1025」[SCOI2009] 游戏
Descriptionwindy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。如：123456对应的关系为1->22->33->14->55->46->6windy的操作如下123456231546312456123546231456312546123456这时，我们就...
02014年9月13日7,522递推与动规,筛法

「NOIP模拟赛」数位和乘积
「题目描述」一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意，这里的N位数是可以有前导零的。比如01，02视为二位数，但是他们的数位和乘积都是0。「输入格式」一行两个整数N，K「输出格式」一个行一个整数表示结果。「样例输入」23「样例输出」2「样例输入2」20「样例输出2」19「数据范围」对于20%：N<=6。对于50%：N<=16存在另外30%：K=0。对于100%：N<=50，0...
02014年9月13日4,186背包动规,高精度
「BZOJ2364」城市美化
Description城市A需要美化市容市貌，现在有n个楼房排成一列，每个楼房的高都在[1,1000]的范围内。市长请了一批工程师来对其中一些楼房进行修建，使楼房高度得到上升（不能让楼房高度下降），对一栋楼房修建，使其高度上升x，需要x2的费用。当所有修建完成后，我们把相邻两楼高度的绝对值乘以c(0<=c<=1000)，得到的就是城市损失的钱，我们把它同样看作是费用。现在想请你合理安排修建楼房的方案，使得所需费用最小。Input第...
32014年9月13日4,254递推与动规,单调栈
「NOIP模拟赛」琪露诺
题目描述在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。小河可以看作一列格子依次编号为0到N，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子i时，她只会移动到i+L到i+R中的一格。你问为什么她这么移动，这还不简单...
22014年9月10日3,140递推与动规
「BZOJ1655」[Usaco2006 Jan] Dollar Dayz 奶牛商店
DescriptionFarmerJohngoestoDollarDaysatTheCowStoreanddiscoversanunlimitednumberoftoolsonsale.Duringhisfirstvisit,thetoolsaresellingvariouslyfor$1,$2,and$3.FarmerJohnhasexactly$5tospend.Hecanbuy5toolsat$1eachor1toolat$3andanadditional1toolat$2.Ofcourse,thereareothercombinationsforatotalof5differentwaysFJcanspendallhismoneyontools.Heretheyare:1@US$3+1@US$21@US$3+2@US$11@US$...
02014年9月5日4,602背包动规,高精度
「BZOJ1044」[HAOI2008] 木棍分割
Description有n根木棍,第i根木棍的长度为Li,n根木棍依次连结了一起,总共有n-1个连接处.现在允许你最多砍断m个连接处,砍完后n根木棍被分成了很多段,要求满足总长度最大的一段长度最小,并且输出有多少种砍的方法使得总长度最大的一段长度最小.并将结果mod10007。。。Input输入文件第一行有2个数n,m.接下来n行每行一个正整数Li,表示第i根木棍的长度.Output输出有2个数,第一个数是总长度最大的一段的长度最小值,第二个数是有多少种...
02014年9月2日5,503递推与动规
「JoyOI1864」[Poetize I] 守卫者的挑战
描述Description　　打开了黑魔法师Vani的大门，队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然，眼前一道亮光闪过。“我，Nizem，是黑魔法圣殿的守卫者。如果你能通过我的挑战，那么你可以带走黑魔法圣殿的地图……”瞬间，队员们被传送到了一个擂台上，最初身边有一个容量为K的包包。擂台赛一共有N项挑战，各项挑战依次进行。第i项挑战有一个属性ai，如果ai>=0，表示这次挑战成功后可以再获得一个...
62014年8月27日4,280递推与动规,概率与期望
「CF461B」Appleman and Tree
Applemanhasatreewith n vertices.Someofthevertices(atleastone)arecoloredblackandotherverticesarecoloredwhite.Considerasetconsistingof k (0 ≤ k < n) edgesofAppleman'stree.IfApplemandeletestheseedgesfromthetree,thenitwillsplitinto (k + 1) parts.Note,thateachpartwillbeatreewithcoloredvertices.NowApplemanwonders,whatisthenumberofsetssplittingthetreeinsuchawaythateachresultingp...
02014年8月27日5,099树形动规
「CF459E」Pashmak and Graph
Pashmak'shomeworkisaproblemaboutgraphs.Althoughhealwaystriestodohishomeworkcompletely,hecan'tsolvethisproblem.Asyouknow,he'sreallyweakatgraphtheory;sotrytohelphiminsolvingtheproblem.Youaregivenaweighteddirectedgraphwith n verticesand m edges.Youneedtofindapath(perhaps,non-simple)withmaximumnumberofedges,suchthattheweightsoftheedgesincreasealongthepath.Inotherwords,eachedgeofthepathmustha...
02014年8月20日2,938递推与动规
「NOIP模拟赛by wulala」公主的工作
和bzoj1046并没多大差别吧。。。[crayon-690c3a523ec70074950732/]
02014年8月16日3,100递推与动规,贪心
「BZOJ1046」[HAOI2007] 上升序列
Description对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1<x2<…<xm)且（ax1<ax2<…<axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impo...
32014年8月15日8,361递推与动规,贪心
「CF455A」Boredom
Alexdoesn'tlikeboredom.That'swhywheneverhegetsbored,hecomesupwithgames.Onelongwintereveninghecameupwithagameanddecidedtoplayit.Givenasequence a consistingof n integers.Theplayercanmakeseveralsteps.Inasinglestephecanchooseanelementofthesequence(let'sdenoteit ak)anddeleteit,atthatallelementsequalto ak + 1 and ak - 1 alsomustbedeletedfromthesequence.Thatstepbrings ak pointstothe...
02014年8月12日3,516递推与动规