动态规划 - Page 22

「BZOJ1296」[SCOI2009] 粉刷匠
Descriptionwindy有N条木板需要被粉刷。每条木板被分为M个格子。每个格子要被刷成红色或蓝色。windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷T次，他最多能正确粉刷多少格子？一个格子如果未被粉刷或者被粉刷错颜色，就算错误粉刷。Input输入文件paint.in第一行包含三个整数，NMT。接下来有N行，每行一个长度为M的字符串，'0'表示红色，'1'表示蓝色...
12014年5月20日5,360递推与动规,背包动规

「BZOJ1233」[Usaco2009Open] 干草堆tower
Description奶牛们讨厌黑暗。为了调整牛棚顶的电灯的亮度，Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草（1<=N<=100000）(从1到N编号)依靠传送带连续的传输进牛棚来。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1.Bessie必须利用所有N包干草来建立起干草堆，并且按照他们进牛棚的顺序摆放。她可以相放多少包就放多少包来建立起tower的地基（当然是紧紧的放在...
12014年5月20日5,235递推与动规,单调队列
「BZOJ1668」[Usaco2006 Oct] Cow Pie Treasures 馅饼里的财富
Description最近，奶牛们热衷于把金币包在面粉里，然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币，并且，这个数字被醒目地标记在馅饼表面。奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上，当然，你可以拿到那块馅饼里的所有金币。你必须从现在的位置，走到草地的另一边，在坐标为(R,C)的馅饼旁边停止走动。每做一次移动，...
02014年5月20日3,192递推与动规
「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会
DescriptionBessie正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。每个奶牛居住在N(1<=N<=100,000)个农场中的一个，这些农场由N-1条道路连接，并且从任意一个农场都能够到达另外一个农场。道路i连接农场A_i和B_i(1<=A_i<=N;1<=B_i<=N),长度为L_i(1<=L_i<=1,000)。集会可以在N个农场中的任意一个举行。另外，每个牛棚中居...
02014年5月19日4,187贪心,树形动规
「BZOJ1231」[Usaco2008 Nov] mixup2 混乱的奶牛
Description混乱的奶牛[DonPiele,2007]FarmerJohn的N(4<=N<=16)头奶牛中的每一头都有一个唯一的编号S_i(1<=S_i<=25,000).奶牛为她们的编号感到骄傲,所以每一头奶牛都把她的编号刻在一个金牌上,并且把金牌挂在她们宽大的脖子上.奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感.如果一个队伍里任意两头相邻的奶牛的编号相差超过K(1<=K<=3400),它就被称为是混乱的.比如说，当N=6,K=1时,1,3,5,2,6...
02014年5月19日3,503状压动规
「BZOJ1096」[ZJOI2007] 仓库建设
DescriptionL公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工...
22014年5月18日5,565斜率优化
「BZOJ1911」[Apio2010] 特别行动队commando
DescriptionInputOutputSampleInput4-110-202234SampleOutput9HINT题解我发现似乎掌握了特殊的斜率优化技巧，我会假装四处看风景dp方程：f[i]=max(f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c)如果j>k且j比k更优f[j]-f[k]+a*sum[j]^2-a*sum[k]^2+b*(sum[k]-sum[j])>2*a*(sum[j]-sum[k])*sum[i][crayon-6743bd05e498a329463327/] ...
22014年5月18日6,211斜率优化
「BZOJ1597」[Usaco2008 Mar] 土地购买
Description农夫John准备扩大他的农场,他正在考虑N(1<=N<=50,000)块长方形的土地.每块土地的长宽满足(1<=宽<=1,000,000;1<=长<=1,000,000).每块土地的价格是它的面积,但FJ可以同时购买多快土地.这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换.如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25.FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费.他需要你帮助他...
22014年5月18日6,569斜率优化
「BZOJ1898」Swamp 沼泽鳄鱼
Description潘塔纳尔沼泽地号称世界上最大的一块湿地，它地位于巴西中部马托格罗索州的南部地区。每当雨季来临，这里碧波荡漾、生机盎然，引来不少游客。为了让游玩更有情趣，人们在池塘的中央建设了几座石墩和石桥，每座石桥连接着两座石墩，且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放，原因是池塘里有不少危险的食人鱼。豆豆先生酷爱冒险，他一听说这个消息，立马赶到了池塘，想做第一个在桥上旅游的...
02014年5月17日5,460递推与动规,矩阵乘法
「JoyOI1608」小熊分糖
背景BackgroundAndyBear 生日模拟赛第二题描述Description晴朗的上午，小熊BIBO抱着一罐糖，出去找好朋友，两只小兔子。从小熊家出来，穿过小树林，在一个有向日葵的路口向右拐，这就是小兔子家了。小熊BIBO见到好朋友，开心的不得了，BIBO要做的第一件事，是分糖，因为大熊说过，好东西是不可以独享的。糖罐里有N颗糖，小熊BIBO要挑出m颗来给两只小兔子，剩下的留着自己吃。对于这n颗糖中的每一颗，这两...
02014年5月17日4,053背包动规
「JoyOI1519」博彩游戏
背景BackgroundBob最近迷上了一个博彩游戏……描述Description这个游戏的规则是这样的：每花一块钱可以得到一个随机数R，花上N块钱就可以得到一个随机序列；有M个序列，如果某个序列是产生的随机序列的子串，那么就中奖了，否则不中。Bob会告诉你这M个序列，和身上有的钱的总数N，当然还有R的范围。请你告诉Bob中奖的概率有多少？输入格式InputFormat第一行三个用空格隔开的数N、M和R的范围R。其中1<=R<=9...
02014年5月11日3,664递推与动规,AC自动机
「NOIP模拟赛」数列
「题目描述」a[1]=a[2]=a[3]=1a[x]=a[x-3]+a[x-1] (x>3)求a数列的第n项对1000000007（10^9+7）取余的值。「输入格式」第一行一个整数T，表示询问个数。以下T行，每行一个正整数n。「输出格式」每行输出一个非负整数表示答案。「样例输入」36810「样例输出」4919「数据范围」对于30%的数据n<=100；对于60%的数据n<=2*10^7；对于100%的数据T<=100，n<=2*10^9；题解这个可以直接矩阵乘法搞掉。。[crayon-6743bd05e...
32014年5月10日3,996递推与动规,矩阵乘法