递推与动规 - Page 14

「BZOJ2326」[HNOI2011] 数学作业
Description题解(F[n]) (10^k 1 1 )(F[n-1])( n )=( 0 1 1 )( n-1 )( 1 ) ( 0 0 1 )( 1 )然后分段矩阵乘法0-9,10-99…10^k-n[crayon-6905a51cb1062140605599/] ...
52014年4月28日7,733递推与动规,矩阵乘法

「BZOJ1677」[Usaco2005 Jan] Sumsets 求和
DescriptionFarmerJohncommandedhiscowstosearchfordifferentsetsofnumbersthatsumtoagivennumber.Thecowsuseonlynumbersthatareanintegerpowerof2.Herearethepossiblesetsofnumbersthatsumto7:1)1+1+1+1+1+1+12)1+1+1+1+1+23)1+1+1+2+24)1+1+1+45)1+2+2+26)1+2+4HelpFJcountallpossiblerepresentationsforagivenintegerN(1<=N<=1,000,000).给出一个N(1≤N≤10^6)，使用一些2的若干次幂的数相加来求之．问有多少...
02014年4月8日4,133递推与动规
「CF415D」Mashmokh and ACM
Mashmokh'sboss,Bimokh,didn'tlikeMashmokh.Sohefiredhim.MashmokhdecidedtogotouniversityandparticipateinACMinsteadoffindinganewjob.HewantstobecomeamemberofBamokh'steam.Inordertojoinhewasgivensomeprogrammingtasksandoneweektosolvethem.Mashmokhisnotaveryexperiencedprogrammer.Actuallyheisnotaprogrammeratall.Sohewasn'tabletosolvethem.That'swhyheaskedyoutohelphimwiththesetasks.Oneofthesetas...
02014年4月7日3,643递推与动规,筛法
「ch30」摆花
背景及描述艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。输入格式输入有1+m行，第一行有两个用空格隔开的正整数n、m，m表示花的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位...
02014年4月5日5,009递推与动规,矩阵乘法
「BZOJ1669」[Usaco2006 Oct] Hungry Cows饥饿的奶牛
DescriptionFarmerJohn养了N(1<=N<=5,000)头奶牛，每头牛都有一个不超过32位二进制数的正整数编号。FJ希望奶牛们在进食前，能按编号从小到大的顺序排好队，但奶牛们从不听他的话。为了让奶牛们养成这个习惯，每次开饭时，FJ从奶牛中顺序地挑出一些，这些奶牛的编号必须按挑出的顺序递增。然后FJ让被挑出的奶牛们吃饭——其他奶牛就只能饿肚子了。现在，你得到了这一次开饭前队伍中从前到后所有奶牛的编号。奶牛们...
02014年4月5日3,877递推与动规,二分法
「NOIP模拟赛」DNA序列
题目描述来自JSSI（JinkelaStateScientificInstitute）的科学家们尝试制造一个长度为N并且只包含A的DNA序列，不出意外地失败了。他们得到了一个含有A和B两种部件的序列。现在他们打算对实验结果进行篡改，来得到一个全部是A的序列。篡改的方式有两种：1更改某一位上部件的状态（A变成B，B变成A）2更改某个前缀内所有部件的状态两种操作的代价都为1。你的任务自然是求最小代价。输入第一行为N，序列长度。第二...
02014年4月5日3,570递推与动规
「BZOJ1616」[Usaco2008 Mar] Cow Travelling游荡的奶牛
Description奶牛们在被划分成N行M列(2<=N<=100;2<=M<=100)的草地上游走，试图找到整块草地中最美味的牧草。FarmerJohn在某个时刻看见贝茜在位置(R1,C1)，恰好T(0<T<=15)秒后，FJ又在位置(R2,C2)与贝茜撞了正着。FJ并不知道在这T秒内贝茜是否曾经到过(R2,C2)，他能确定的只是，现在贝茜在那里。设S为奶牛在T秒内从(R1,C1)走到(R2,C2)所能选择的路径总数，FJ希望有一个程序来帮他计算...
02014年4月4日4,177递推与动规
[FJOI2014] 石子合并问题
问题描述有n堆石子，每堆1个，要合并成一堆，规定每次可以任意选两堆合并成新的一堆，两堆中较少的石子数记为该次合并的得分。输入n输出最大得分样例输入7样例输出9O（n）做法[crayon-6905a51cb4de0647500963/]O（nlogn）堆ndsf神犇秒杀[crayon-6905a51cb4de9314982523/] ...
22014年3月31日7,453递推与动规,堆
「cogs754」[USACO Open09] 滑雪训练
农夫约翰想带着他的奶牛Bessie去佛罗里达滑雪，可是，Bessie的滑雪技术真是太差了。她了解到滑雪学校全天提供滑雪课程，共有S(0<=S<=100)个滑雪课程可供选择，课程i从时间M_i(1<=M_i<=10,000)开始，持续时间为L_i(1<=L_i<=10,000)，学完该课程滑雪水平将提升至A_i(1<=A_i<=100)，注意：滑雪水平的提升是绝对的，而不是累加的。此外Bessie还买了一张滑雪练习场的地图，从图中可以看到练习场每个...
02014年3月31日3,612递推与动规
「BZOJ1609」[Usaco2008 Feb] Eating Together麻烦的聚餐
Description为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。第i头奶牛有一张标明她用餐批次D_i(1<=D_i<=3)的卡片。虽然所有N(1<=N<=30,000)头奶牛排成了很整齐的队伍但谁都看得出来，卡...
02014年3月29日4,095递推与动规
「hdu2294」Pendant
ProblemDescriptionOnSaintValentine'sDay,AleximaginedtopresentaspecialpendanttohisgirlfriendmadebyKkindofpearls.Thependantisactuallyastringofpearls,anditslengthisdefinedasthenumberofpearlsinit.Asisknowntoall,Alexisveryrich,andhehasNpearlsofeachkind.Pendantcanbetoldapartaccordingtopermutationofitspearls.Nowhewantstoknowhowmanykindofpendantcanhemade,withlengthbetween1andN.Ofcour...
02014年3月27日3,225递推与动规,矩阵乘法
「BZOJ1222」[HNOI2001] 产品加工
Description某加工厂有A、B两台机器，来加工的产品可以由其中任何一台机器完成，或者两台机器共同完成。由于受到机器性能和产品特性的限制，不同的机器加工同一产品所需的时间会不同，若同时由两台机器共同进行加工，所完成任务又会不同。某一天，加工厂接到n个产品加工的任务，每个任务的工作量不尽一样。你的任务就是：已知每个任务在A机器上加工所需的时间t1,B机器上加工所需的时间t2及由两台机器共同加工所需的时间t3，请...
02014年3月24日3,870递推与动规