动态规划 - Page 4

「省选模拟赛」小奇挖矿 3
原题：「泉七培训-刘定峰」物流「题目背景」小奇在喵星系使用了无限非概率驱动的采矿机，以至于在所有星球上都采出了一些矿石，现在它准备建一些矿石仓库并把矿石运到各个仓库里。「问题描述」喵星系有n个星球，标号为1到n，星球以及星球间的航线形成一棵树。所有星球间的双向航线的长度都为1。小奇要在若干个星球建矿石仓库，设立每个仓库的费用为K。对于未设立矿石仓库的星球，设其到一个仓库的距离为i，则将矿石运回的费用为D...
02015年12月17日6,361递推与动规,深度搜索,广度搜索

「省选模拟赛」[hdu5171] 小奇的集合
注：原题没有考虑最大值为负数的情况「题目背景」小奇总是在数学课上思考奇怪的问题。「问题描述」有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大值。（数据保证这个值为非负数）「输入格式」第一行有两个整数n,k表示初始元素数量和操作数，第二行包含n个整数表示初始时可重集的元素。「输出格式」输出一个整数，表示和的最大值。答案对10000007取模。「样例输入」2236...
02015年11月22日4,520递推与动规,矩阵乘法
「NOIP模拟赛」[hdu5492] 小奇的矩阵
「题目背景」小奇总是在数学课上思考奇怪的问题。「问题描述」给定一个n*m的矩阵，矩阵中的每个元素aij为正整数。接下来规定1.合法的路径初始从矩阵左上角出发，每次只能向右或向下走，终点为右下角。2.路径经过的n+m-1个格子中的元素为A1,A2…A(n+m-1)，Aavg为Ai的平均数，路径的V值为(n+m-1)*∑(Ai-Aavg)^2(1<=i<=n+m-1)求V值最小的合法路径，输出V值即可，有多组测试数据。「输入格式」第一行包含一个正整数T，...
62015年10月5日5,703递推与动规,深度搜索
「NOIP模拟赛」小奇挖矿 2
原题：streaming_3noip模拟赛4和7「题目背景」小奇飞船的钻头开启了无限耐久+精准采集模式！这次它要将原矿运到泛光之源的矿石交易市场，以便为飞船升级无限非概率引擎。「问题描述」现在有m+1个星球，从左到右标号为0到m，小奇最初在0号星球。有n处矿体，第i处矿体有ai单位原矿，在第bi个星球上。由于飞船使用的是老式的跳跃引擎，每次它只能从第x号星球移动到第x+4号星球或x+7号星球。每到一个星球，小奇会采走该星球上所有的原矿...
22015年10月5日5,190递推与动规
「BZOJ4203」「FJ2015集训」同桌的你
「问题描述」同桌的你(deskmate.cpp/c/pas)每学期最让人激动的时候莫过于换同桌了,没有一位学生不愿意和自己喜欢的同学坐在一起,度过一个愉快充实的学期。作为一位民主的教师,小A会收集每个学生的同桌意向作为参考,每个学生会向小A提交一个他(或她)理想中的同桌。小A希望他能够满足尽可能多的同学的要求,当然,每位同学只能有一个同桌。换句话说,小A希望能够出现尽可能多的同桌,满足同桌两人中存在着一个人,喜欢和另一个人为同桌...
42015年7月14日5,137树形动规
「CF268D」Wall Bars
Manaoisworkingforaconstructioncompany.Recently,anordercametobuildwallbarsinachildren'spark.Manaowascommissionedtodevelopaplanofconstruction,whichwillenablethecompanytosavethemostmoney.Afterreviewingtheformalspecificationsforthewallbars,Manaodiscoveredanumberofcontroversialrequirementsanddecidedtotreatthemtothecompany'sadvantage.Hisresultingdesigncanbedescribedasfollows:Let'sintroducesomeuni...
22015年7月6日4,712递推与动规
「CF316D3」PE Lesson
SmartBeaverdecidedtobenotonlysmart,butalsoahealthybeaver!AndsohebegantoattendphysicaleducationclassesatschoolX.Inthisschool,physicaleducationhasaverycreativeteacher.Oneofhisfavoritewarm-upexercisesisthrowingballs.Studentslineup.Eachonegetsasingleballinthebeginning.Theballsarenumberedfrom1ton(bythedemandoftheinventorycommission).Figure1.Theinitialpositionforn = 5.Afterreceivingtheball...
02015年7月5日3,455递推与动规
NOI2005瑰丽华尔兹
Description你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼•布德曼•T.D.•柠檬•1900，朋友们都叫他1900。1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上，很不幸他刚出生就被抛弃了，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的...
02015年6月29日7,620递推与动规,单调队列
「CF261X」Codeforces Round #160 (Div. 1)
A.MaximandDiscounts挑要求最小的优惠方案啦，最贵的那几个显然要花钱买，赠品当然也是选最贵的。。。恩变成了子问题[crayon-68e99f0c49f61800254861/]B.MaximandRestaurantf(i,j,k)表示前i个人，选了j个，消耗为k的方案数然后枚举选的人数+组合数学，注意不重复统计答案[crayon-68e99f0c49f6a020243042/]C.MaximandMatrix发现第m+1行的和就是2^(m二进制1的个数+1)则t是2的幂次才有解，求<=n的ans数量从大到小枚举每一...
32015年6月25日4,519递推与动规,贪心,深度搜索,排列组合
「CF332X」Codeforces Round #193 (Div. 2)
A.DowntheHatch!阅读+模拟题[crayon-68e99f0c3a5fc694187064/]B.MaximumAbsurdity每K个的和求出来以后，就是找距离超过K的两个数相加的最大值[crayon-68e99f0c3a604109206386/]C.Students'Revengehttp://m.blog.csdn.net/blog/u010638776/10044315[crayon-68e99f0c3a60a657294466/]D.TheftofBlueprintswmd神犇：http://blog.csdn.net/wmdcstdio/article/details/44755115[crayon-68e99f0c3a60f895264341/]E.Binary...
02015年6月25日3,582模拟,递推与动规,堆,贪心,记忆化搜索
「CF360X」Codeforces Round #210 (Div. 1)
A.LevkoandArrayRecovery求出每个位置初始值的最大值，然后check一下[crayon-68e99f0c4a8b1493636683/]B.LevkoandArray二分答案，f(i)表示前i个的最小修改次数，且i不修改，枚举上一个不修改的位置转移[crayon-68e99f0c4a8bc495119969/]C.LevkoandStringsf(i,j)表示前i个字母，beauty值为j的合法方案，\(t_k=s_k\)(k>j)1.在第i位放一个比s[i]大的字母，枚举上一个位置i-k-1满足\(s_{i-k-1}!=t_{i-k-1}\)产生的新的bea...
12015年6月23日5,481递推与动规,贪心,spfa,二分法,最大公约数与最小公倍数
「CF335X」MemSQL start[c] up Round 2 – online version
A.Banana枚举sheet数，找到第一个不能用已有sticker凑出的[crayon-68e99f0c3ab6a336093111/]B.Palindromef(i,j)表示末尾在i之前，长度为j的回文序列的最大头位置[crayon-68e99f0c3ab74962716129/]C.MoreReclamation用(len,x,y)表示一个游戏状态，2*len的完整格子，左端的状态为x，右端的状态为yx，y=0/1/2分别表示（完整），（左侧/右侧第一行第一格不可删），（左侧/右侧第二行第一格不可删）边界情况：len=0时sg值为0len=...
12015年6月23日4,348递推与动规,模拟,贪心,STL,博弈论,记忆化搜索,概率与期望