1622: [Usaco2008 Open]Word Power 名字的能量
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 462 Solved: 228 [Submit][Status][Discuss]
Description
约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串， 约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少能量．所谓“蕴含”，是指某个能量字符串的所 …
阅读更多1621: [Usaco2008 Open]Roads Around The Farm分岔路口
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 698 Solved: 513 [Submit][Status][Discuss]
Description
约翰的N(1≤N≤1,000,000,000)只奶牛要出发去探索牧场四周的土地．她们将沿着一条路走，一直走到三岔路口（可以认为所有的路口都是这样的）．这时候，这一群奶牛可能会分成两群，分别沿着接下来的两条路继续走．如果她们再次走到三岔路口，那么仍有可能继续分裂成两群继续走． 奶牛的分裂方式十分古怪：如果这一群奶牛可以精确地分成两部 …
阅读更多1620: [Usaco2008 Nov]Time Management 时间管理
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 636 Solved: 387 [Submit][Status][Discuss]
Description
Ever the maturing businessman, Farmer John realizes that he must manage his time effectively. He has N jobs conveniently numbered 1..N (1 <= N <= 1,000) to accomplish …
阅读更多1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 661 Solved: 292 [Submit][Status][Discuss]
Description
The farm has many hills upon which Farmer John would like to place guards to ensure the safety of his valuable milk-cows. He wonders how many guards he will need if he wishes …
阅读更多1618: [Usaco2008 Nov]Buying Hay 购买干草
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 906 Solved: 456 [Submit][Status][Discuss]
Description
约翰的干草库存已经告罄，他打算为奶牛们采购日(1≤日≤50000)磅干草．
他知道N(1≤N≤100)个干草公司，现在用1到N给它们编号．第i个公司卖的干草包重量为Pi(1≤Pi≤5000)磅，需要的开销为Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包． 帮助约翰找到最小的开销来满足需要，即采购到至 …
阅读更多1617: [Usaco2008 Mar]River Crossing渡河问题
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 837 Solved: 606 [Submit][Status][Discuss]
Description
Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。 由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。 当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1 <= M <= …
阅读更多1616: [Usaco2008 Mar]Cow Travelling游荡的奶牛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1012 Solved: 553 [Submit][Status][Discuss]
Description
奶牛们在被划分成N行M列(2 <= N <= 100; 2 <= M <= 100)的草地上游走，试图找到整块草地中最美味的牧草。Farmer John在某个时刻看见贝茜在位置 (R1, C1)，恰好T (0 < T <= 15)秒后，FJ又在位置(R2, C2)与贝茜撞了正着。 FJ并不知道在这T秒内贝茜是否曾经 …
阅读更多1613: [Usaco2007 Jan]Running贝茜的晨练计划
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1468 Solved: 706 [Submit][Status][Discuss]
Description
奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。 贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲 …
阅读更多1612: [Usaco2008 Jan]Cow Contest奶牛的比赛
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 900 Solved: 597 [Submit][Status][Discuss]
Description
FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A …
阅读更多1611: [Usaco2008 Feb]Meteor Shower流星雨
Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1239 Solved: 537 [Submit][Status][Discuss]
Description
去年偶们湖南遭受N年不遇到冰冻灾害，现在芙蓉哥哥则听说另一个骇人听闻的消息： 一场流星雨即将袭击整个霸中，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽， 届时将会对它撞到的一切东西造成毁灭性的打击。很自然地，芙蓉哥哥开始担心自己的 安全问题。以霸中至In型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方 （也就是说，一块不会被任何流星砸到的土 …
阅读更多1609: [Usaco2008 Feb]Eating Together麻烦的聚餐
Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1282 Solved: 766 [Submit][Status][Discuss]
Description
为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。 …
阅读更多首先回顾一下n^2的做法。 状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j])
1for ( int i = 1 ; i <= n ; i++) cin>>a[i]; 2 3 for ( int i = 1 ; i <= n ; i++) 4 { 5 dp[i] = 1; 6 for ( int j = 1 ; j < i ; j++) 7 { 8 if (a[i]>a[j]) 9 dp[i] = max(dp[i],dp[j]+1); 10 } 11 …
阅读更多1599: [Usaco2008 Oct]笨重的石子
Time Limit: 10 Sec Memory Limit: 162 MB Submit: 886 Solved: 614 [Submit][Status][Discuss]
Description
贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。 问题给出三个骰子的面数，让你求出出 …
阅读更多Time Limit: 5 Sec Memory Limit: 64 MB Submit: 774 Solved: 593 [Submit][Status][Discuss]
Description
Farmer John有一个过时的打谷机（收割小麦），它需要带子来带动。发动机驱动轮1总是顺时针旋转的，用来带动转轮2，转轮2来带动转轮3，等等。一共有n（2<=n<=1000）个转轮（n-1条带子）。上面的图解描述了转轮的两种连接方式，第一种方式使得两个轮子旋转的方向相同，第二种则相反。 给出一串带子的信息： *Si—驱动轮 *Di—被动轮 *Ci—连接的类型（0=直接连接，1=交叉连接） 不幸的是，列出的信息是随即 …
阅读更多Description
N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。
阅读更多1601: [Usaco2008 Oct]灌水
Time Limit: 5 Sec Memory Limit: 162 MB Submit: 1624 Solved: 1059 [Submit][Status][Discuss]
Description
Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最 …
阅读更多勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意： *只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。
阅读更多