背包动规 - hzwer.com

【LOJ】小奇 NOIP 练习题
可以在https://loj.ac/problems/tag/207AC这些题目小奇采药小奇取石子小奇的旅行计划小奇探险小奇采药对于30%的数据，$O(2^n)$枚举取or不取对于60%的数据，$O(nm)$做01背包，即$f(i,j)$表示前i株草药，耗费j的时间能达到的最大代价。对于100%的数据，注意到m,t,v纯随机那么不会选太多的草药，而耗时较少的草药有很大概率存在于最优解中针对这些性质优化搜索当然也可以合理使用随机化和卡时，复杂度O(玄学)小奇取石子在n...
22019年4月5日6,113递推与动规,深度搜索,背包动规

「CF685X」Codeforces Round #360 (Div. 1)
A.NP-HardProblem二分图染色[crayon-6767edfcf0588919421554/]B.RemaindersGame将K分解为a1^p1*a2^p2...an^pn则ai^pi要被c中的某个数整除[crayon-6767edfcf0594653115842/]C.TheValuesYouCanMake用f(i,j)表示容量i和j的背包能不能同时取得若f(x,K-x)则可以用K中的物品凑出X[crayon-6767edfcf0598015228079/] ...
02016年6月30日2,070背包动规,二分图染色,最大公约数与最小公倍数
POJ训练记录4
1694.AnOldStoneGamef[x]表示x为根的树至少需要的石头，把子树按f排序后贪心即可[crayon-6767edfcf15a5525029119/]poj1738.AnoldStoneGame参见discuss的神算法，据说是knuth提出的？[crayon-6767edfcf15af061304520/]1737.ConnectedGraph跪大爷http://blog.csdn.net/PoPoQQQ/article/details/43525019[crayon-6767edfcf15b6807224660/]1742.Coins二进制拆分+bitset竟然过不了...我被题解骗了突然一想这不是以前做过...
02015年5月20日4,514递推与动规,模拟,贪心,背包动规,树形动规,几何,排列组合
「BZOJ1334」[Baltic2008] Elect
DescriptionN个政党要组成一个联合内阁，每个党都有自己的席位数.现在希望你找出一种方案，你选中的党的席位数要大于总数的一半，并且联合内阁的席位数越多越好.对于一个联合内阁，如果某个政党退出后，其它党的席位仍大于总数的一半，则这个政党被称为是多余的，这是不允许的.Input第一行给出有多少个政党.其值小于等于300下面给出每个政党的席位数.总席位数小于等于100000Output你的组阁方案中最多能占多少个席位.SampleIn...
22014年12月16日3,640背包动规
「NOIP模拟赛」篮球比赛2
由于Czhou举行了众多NOIP模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当...
12014年11月5日4,867背包动规,深度搜索,状压动规
「BZOJ3687」「FJ2014集训」简单题
「题目描述」小呆开始研究集合论了，他提出了关于一个数集四个问题：1.子集的异或和的算术和。2.子集的异或和的异或和。3.子集的算术和的算术和。4.子集的算术和的异或和。目前为止，小呆已经解决了前三个问题，还剩下最后一个问题还没有解决，他决定把这个问题交给你，未来的集训队队员来实现。「输入格式」从xor.in中输入数据第一行，一个整数n。第二行，n个正整数，表示a1,a2,...,an「输出格式」输出到xor.out中一行，包含一个整...
22014年9月14日6,283深度搜索,背包动规
「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日3,819背包动规,高精度
「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,008背包动规,高精度
「czy系列赛」蒟蒻czy又被D飞了
（本题中的图片忽略）「题目描述」机房里的各路巨神天天D蒟蒻CZY，早已是他们的日常任务了。（今天的机房也是很和平呢）这一次他们安排好了一种方式来D蒟蒻Czy。每个人每次都能把CzyD飞一个高度（让Czy的高度+a[i]），由于他们的精♂力有限（尤其是某些后宫王），要保留体力应对接下来的战♂斗，所以他们每个人只会DCzyk[i]次。由于他们每个人的D人能力不同，各有所长，所以他们每个人都在Czy到一定高度h[i]以后良心发...
32014年7月19日3,613背包动规
「czy系列赛」czy的后宫5
czy的后宫5描述czy要召集他的妹子，但是由于条件有限，可能每个妹子不能都去，但每个妹子都有一个美丽值，czy希望来的妹子们的美丽值总和最大（虽然……）。czy有一个周密的电话通知网络，它其实就是一棵树，根结点为czy，他可以通知一些妹子（毕竟他不认识他的所有妹子嘛），称为他的下线（也就是儿子节点），下线们继续通知自己的下线。任何妹子都可以不去，但是任何一个妹子如果要去，则她的上线（也就是她的父亲节点）一定要去...
12014年7月19日5,097背包动规
「NOIP模拟赛」笨笨当粉刷匠
笨笨太好玩了，农田荒芜了，彩奖用光了，笨笨只好到处找工作，笨笨找到了一份粉刷匠的工作。笨笨有n条木板需要被粉刷。每条木板被分成m个格子，每个格子要被刷成红色或蓝色。笨笨每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色，已知每个格子最多只能被粉刷一次。如果笨笨只能粉刷t次，他最多能正确粉刷多少格子。一个格子如果未被粉刷或被粉刷成错误颜色，就算粉刷错误。「输入格式」第一行三个数n，m，t；接下来...
02014年7月8日3,690递推与动规,背包动规
「BZOJ1004」[HNOI2008] Cards
Description小春现在很清闲,面对书桌上的N张牌,他决定给每张染色,目前小春只有3种颜色:红色,蓝色,绿色.他询问Sun有多少种染色方案,Sun很快就给出了答案.进一步,小春要求染出Sr张红色,Sb张蓝色,Sg张绝色.他又询问有多少种方案,Sun想了一下,又给出了正确答案.最后小春发明了M种不同的洗牌法,这里他又问Sun有多少种不同的染色方案.两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可...
22014年5月26日9,337背包动规,置换,乘法逆元