动态规划 - Page 20

「NOIP模拟赛」秘密文件
「问题描述」某天，情报局得到了一份秘密文件。文件的内容是加密后的全部由大写字母组成字符串。情报局局长小明想将其发送给远在东方神秘的xx大陆上的老朋友小刘来解密。然而若字符串太长，则需要很长的发送时间，太不安全了，因此小明想尽量将其缩短。于是小明制定了这样一个缩短规则：若一个字符串t连续出现k次，则可以用k(t)进行说明。如ABABAB可以缩成3(AB)。当然，重复缩短是允许的，如ABABABAAAAAAARA...
02014年7月10日3,855区间动规

「NOIP模拟赛」笨笨当粉刷匠
笨笨太好玩了，农田荒芜了，彩奖用光了，笨笨只好到处找工作，笨笨找到了一份粉刷匠的工作。笨笨有n条木板需要被粉刷。每条木板被分成m个格子，每个格子要被刷成红色或蓝色。笨笨每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色，已知每个格子最多只能被粉刷一次。如果笨笨只能粉刷t次，他最多能正确粉刷多少格子。一个格子如果未被粉刷或被粉刷成错误颜色，就算粉刷错误。「输入格式」第一行三个数n，m，t；接下来...
02014年7月8日3,633递推与动规,背包动规
「BZOJ1596」[Usaco2008 Jan] 电话网络
DescriptionFarmerJohn决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1<=N<=10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N顺次编号。所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1<=A<=N;1<=B<=N;A!=B)，都可以找到一个以A开头以B结尾的草地序列，并且序列中相邻的编号所代表的草地...
02014年7月7日4,392贪心,树形动规
「BZOJ1492」[NOI2007] 货币兑换Cash
DescriptionInput第一行两个正整数N、S，分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行，第K行三个实数AK、BK、RateK，意义如题目中所述Output只有一个实数MaxProfit，表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数。SampleInput3100111122223SampleOutput225.000HINT测试数据设计使得精度误差不会超过10-7。对于40%的测试数据，满足N≤10；对于60%的测试数据，满足N≤1...
102014年6月18日9,919递推与动规
「BZOJ1026」[SCOI2009] windy数
Descriptionwindy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。windy想知道，在A和B之间，包括A和B，总共有多少个windy数？Input包含两个整数，AB。Output一个整数。SampleInput「输入样例一」110「输入样例二」2550SampleOutput「输出样例一」9「输出样例二」20「数据规模和约定」20%的数据，满足1<=A<=B<=1000000。100%的数据，满足1<=A<=B<=2000000000。...
32014年6月18日7,052数位动规
「BZOJ3156」防御准备
DescriptionInput第一行为一个整数N表示战线的总长度。第二行N个整数，第i个整数表示在位置i放置守卫塔的花费Ai。Output共一个整数，表示最小的战线花费值。SampleInput102315456312SampleOutput18HINT1<=N<=10^6,1<=Ai<=10^9题解裸的斜率优化把a[i]都反过来sum[i]=sum[i-1]+if[i]=min{f[j]+sum[i-1]-sum[j]-(i-j-1)*j}[crayon-6724ca8c8952a617133227/] ...
02014年6月16日4,338斜率优化
「泉七培训 – 郑予凡」子集
炫教的题解：为叙述方便，我们不妨设S={-n,-n+1,...,n}。本题就转化为求解∑χ(A)。其中求和式取遍S的k元子集A，而χ(A)当A的元素之和为0时返回1，否则返回0。我们给出一些在比赛过程中解决本题的常见的算法。「算法1：枚举」顾名思义，这个算法直接枚举所有可能的A，然后逐一考察χ(A)。期望得分：10「算法2：动态规划」记dp[a][b][c]为“从-n到n，当前已枚举到a∈S并已考虑完其是否在A中，已经确定了b个数在集合A中，...
02014年6月14日3,158递推与动规
「BZOJ1801」[Ahoi2009] chess 中国象棋
Description在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国像棋中炮的行走方式大家应该很清楚吧.Input一行包含两个整数N，M，中间用空格分开.Output输出所有的方案数，由于值比较大，输出其mod9999973SampleInput13SampleOutput7HINT除了在3个格子中都放满炮的的情况外，其它的都可以.100%的数据中N,M不超过10050%的数据中，N,M至少有一个数不超过83...
22014年6月7日3,423递推与动规
「BZOJ1589」[Usaco2008 Dec] Trick or Treat on the Farm 采集糖果
Description每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果．农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖...
02014年6月5日4,166图的连通,记忆化搜索
「CF439D」Devu and his Brother
Devuandhisbrotherloveeachotheralot.Astheyaresupergeeks,theyonlyliketoplaywitharrays.Theyaregiventwoarrays a and b bytheirfather.Thearray a isgiventoDevuand b tohisbrother.AsDevuisreallyanaughtykid,hewantstheminimumvalueofhisarray a shouldbeatleastasmuchasthemaximumvalueofhisbrother'sarray b.NowyouhavetohelpDevuinachievingthiscondition.Youcanperformmultipleoperationsonthearrays...
02014年6月5日2,633递推与动规
「CF440C」One – Based Arithmetic
Prof.Vasechkinwantstorepresentpositiveinteger n asasumofaddends,whereeachaddendsisanintegernumbercontainingonly1s.Forexample,hecanrepresent121as121=111+11+–1.Helphimtofindtheleastnumberofdigits 1 insuchsum.InputThefirstlineoftheinputcontainsinteger n (1 ≤ n < 1015).OutputPrintexpectedminimalnumberofdigits 1.Sampletest(s)input[crayon-6724ca8c8ab10444304718/]output[crayon-67...
02014年6月4日3,490记忆化搜索
「NOIP模拟赛」密码锁
题目描述hzwer有一把密码锁，由N个开关组成。一开始的时候，所有开关都是关上的。当且仅当开关x1,x2,x3,...xk为开，其他开关为关时，密码锁才会打开。他可以进行M种的操作，每种操作有一个size[i]，表示，假如他选择了第i种的操作的话，他可以任意选择连续的size[i]个格子，把它们全部取反。（注意，由于黄金大神非常的神，所以操作次数可以无限>_<）本来这是一个无关紧要的问题，但是，黄金大神不小心他的钱丢进去了，没有...
42014年6月1日5,247费用流,广度搜索,状压动规,记忆化搜索