• 「BZOJ1296」[SCOI2009] 粉刷匠

    「BZOJ1296」[SCOI2009] 粉刷匠

    Descriptionwindy有N条木板需要被粉刷。每条木板被分为M个格子。每个格子要被刷成红色或蓝色。windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷T次,他最多能正确粉刷多少格子?一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。Input输入文件paint.in第一行包含三个整数,NMT。接下来有N行,每行一个长度为M的字符串,'0'表示红色,'1'表示蓝色...

    12014年5月20日5,331递推与动规,背包动规
  • 「BZOJ1233」[Usaco2009Open] 干草堆tower

    「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,215递推与动规,单调队列
  • 「BZOJ1668」[Usaco2006 Oct] Cow Pie Treasures 馅饼里的财富

    「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,173递推与动规
  • 「BZOJ1827」[Usaco2010 Mar] gather 奶牛大集会

    「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,165贪心,树形动规
  • 「BZOJ1231」[Usaco2008 Nov] mixup2 混乱的奶牛

    「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,486状压动规
  • 「BZOJ1096」[ZJOI2007] 仓库建设

    「BZOJ1096」[ZJOI2007] 仓库建设

    DescriptionL公司有N个工厂,由高到底分布在一座山上。如图所示,工厂1在山顶,工厂N在山脚。由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个工...

    22014年5月18日5,541斜率优化
  • 「BZOJ1911」[Apio2010] 特别行动队commando

    「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-6724e6c586c48942442348/] ...

    22014年5月18日6,143斜率优化
  • 「BZOJ1597」[Usaco2008 Mar] 土地购买

    「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,550斜率优化
  • 「BZOJ1898」Swamp 沼泽鳄鱼

    「BZOJ1898」Swamp 沼泽鳄鱼

    Description潘塔纳尔沼泽地号称世界上最大的一块湿地,它地位于巴西中部马托格罗索州的南部地区。每当雨季来临,这里碧波荡漾、生机盎然,引来不少游客。为了让游玩更有情趣,人们在池塘的中央建设了几座石墩和石桥,每座石桥连接着两座石墩,且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放,原因是池塘里有不少危险的食人鱼。豆豆先生酷爱冒险,他一听说这个消息,立马赶到了池塘,想做第一个在桥上旅游的...

    02014年5月17日5,429递推与动规,矩阵乘法
  • 「JoyOI1608」小熊分糖

    「JoyOI1608」小熊分糖

    背景BackgroundAndyBear 生日模拟赛 第二题描述Description晴朗的上午,小熊BIBO抱着一罐糖,出去找好朋友,两只小兔子。从小熊家出来,穿过小树林,在一个有向日葵的路口向右拐,这就是小兔子家了。小熊BIBO见到好朋友,开心的不得了,BIBO要做的第一件事,是分糖,因为大熊说过,好东西是不可以独享的。糖罐里有N颗糖,小熊BIBO要挑出m颗来给两只小兔子,剩下的留着自己吃。 对于这n颗糖中的每一颗,这两...

    02014年5月17日4,035背包动规
  • 「JoyOI1519」博彩游戏

    「JoyOI1519」博彩游戏

    背景BackgroundBob最近迷上了一个博彩游戏……描述Description这个游戏的规则是这样的:每花一块钱可以得到一个随机数R,花上N块钱就可以得到一个随机序列;有M个序列,如果某个序列是产生的随机序列的子串,那么就中奖了,否则不中。Bob会告诉你这M个序列,和身上有的钱的总数N,当然还有R的范围。请你告诉Bob中奖的概率有多少?输入格式InputFormat第一行三个用空格隔开的数N、M和R的范围R。其中1<=R<=9...

    02014年5月11日3,633递推与动规,AC自动机
  • 「NOIP模拟赛」数列

    「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-6724e6c58...

    32014年5月10日3,978递推与动规,矩阵乘法
22 / 33 « 上一页 1 ...20 21 22 23 24 ...33 下一页 »