Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

11/28
22:43
一般动规与递推

[bzoj 1617] Usaco2008Mar River Crossing渡河问题

00:00/00:00

54fbb2fb43166d22bbef1e85402309f79052d203  4610b912c8fcc3ce459dc2229445d688d43f2045

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河,但他们所有的渡河工具,仅仅是一个木筏。 由于奶牛不会划船,在整个渡河过程中,FJ必须始终在木筏上。在这个基础上,木筏上的奶牛数目每增加1,FJ把木筏划到对岸就得花更多的时间。 当FJ一个人坐在木筏上,他把木筏划到对岸需要M(1 <= M <= 1000)分钟。当木筏搭载的奶牛数目从i-1增加到i时,FJ得多花M_i(1 <= M_i <= 1000)分钟才能把木筏划过河(也就是说,船上有1头奶牛时,FJ得花M+M_1分钟渡河;船上有2头奶牛时,时间就变成M+M_1+M_2分钟。后面的依此类推)。那么,FJ最少要花多少时间,才能把所有奶牛带到对岸呢?当然,这个时间得包括FJ一个人把木筏从对岸划回来接下一批的奶牛的时间。

Read More →

[bzoj 1617] Usaco2008Mar River Crossing渡河问题

@krydom2年前

11/28
20:52
一般动规与递推

[bzoj 1609] Usaco2008Feb Eating Together麻烦的聚餐

00:00/00:00

004041dqb6ppyvuqvvuy8a  1418178458390

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐。每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排,晚饭前的排队成了一个大麻烦。 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来,卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后,FJ找到了一种简单些的方法:奶牛们不动,他沿着队伍从头到尾走一遍把那些他认为排错队的奶牛卡片上的编号改掉,最终得到一个他想要的每个组中的奶牛都站在一起的队列,例如111222333或者333222111。哦,你也发现了,FJ不反对一条前后颠倒的队列,那样他可以让所有奶牛向后转,然后按正常顺序进入餐厅。 你也晓得,FJ是个很懒的人。他想知道,如果他想达到目的,那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候,都不会挪位置。

Read More →

[bzoj 1609] Usaco2008Feb Eating Together麻烦的聚餐

@krydom2年前

11/28
19:56
一般动规与递推

[bzoj 1607] Usaco2008Dec Patting Heads 轻拍牛头

00:00/00:00

8644ebf81a4c510f625b58776359252dd52aa5c4  b3b7d0a20cf431ad8b0d59554836acaf2fdd98fa

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

今天是贝茜的生日,为了庆祝自己的生日,贝茜邀你来玩一个游戏.
    贝茜让N(1≤N≤100000)头奶牛坐成一个圈.除了1号与N号奶牛外,i号奶牛与i-l号和i+l号奶牛相邻.N号奶牛与1号奶牛相邻.农夫约翰用很多纸条装满了一个桶,每一张包含了一个独一无二的1到1,000,000的数字.
    接着每一头奶牛i从柄中取出一张纸条Ai.每头奶牛轮流走上一圈,同时拍打所有编号能整除在纸条上的数字的牛的头,然后做回到原来的位置.牛们希望你帮助他们确定,每一头奶牛需要拍打的牛.

Read More →

[bzoj 1607] Usaco2008Dec Patting Heads 轻拍牛头

@krydom2年前

11/27
21:21
一般动规与递推 未分类

[bzoj 1600] [Usaco2008 Oct]建造栅栏

00:00/00:00

d1160924ab18972bf0868ff9e4cd7b899e510a40  a8773912b31bb051b7e33f1b347adab44aede03a (1)

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。

Read More →

[bzoj 1600] [Usaco2008 Oct]建造栅栏

@krydom2年前

10/31
21:24
一般动规与递推

[bzoj 1616] Usaco2008 Mar Cow Travelling游荡的奶牛

00:00/00:00

20130323081435407  20120201140317_JxWFX  5e2853143f1e650225c27bd865741cee

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1),恰好T (0 < T <= 15)秒后,FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经到过(R2, C2),他能确定的只是,现在贝茜在那里。 设S为奶牛在T秒内从(R1, C1)走到(R2, C2)所能选择的路径总数,FJ希望有一个程序来帮他计算这个值。每一秒内,奶牛会水平或垂直地移动1单位距离(奶牛总是在移动,不会在某秒内停在它上一秒所在的点)。草地上的某些地方有树,自然,奶牛不能走到树所在的位置,也不会走出草地。 现在你拿到了一张整块草地的地形图,其中'.'表示平坦的草地,'*'表示挡路的树。你的任务是计算出,一头在T秒内从(R1, C1)移动到(R2, C2)的奶牛可能经过的路径有哪些。

Read More →

[bzoj 1616] Usaco2008 Mar Cow Travelling游荡的奶牛

@krydom2年前

09/5
22:42
一般动规与递推

Usaco2007Jan Running贝茜的晨练计划 [bzoj 1613]

00:00/00:00

10202265372667385350_600x600_220  3020385595298295510_500x707_220  2635113833012388348_500x625_220

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

 奶牛们打算通过锻炼来培养自己的运动细胞,作为其中的一员,贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始,贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地,如果贝茜选择在第i分钟内跑步,她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米,并且她的疲劳度会增加 1。不过,无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息,那么她的疲劳度就会每分钟减少1,但她必须休息到疲劳度恢复到0为止。

Read More →

Usaco2007Jan Running贝茜的晨练计划 [bzoj 1613]