1628: [Usaco2007 Demo]City skyline

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 396  Solved: 317 [Submit][Status][Discuss]

Description

Input

第一行给出N，W

第二行到第N+1行:每行给出二个整数x,y，输入的x严格递增，并且第一个x总是1

Output

输出一个整数，表示城市中最少包含的建筑物数量

1627: [Usaco2007 Dec]穿越泥地

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 624  Solved: 411 [Submit][Status][Discuss]

Description

清早6：00，Farmer John就离开了他的屋子，开始了他的例行工作：为贝茜挤奶。前一天晚上，整个农场刚经受过一场瓢泼大雨的洗礼，于是不难想见，FJ 现在面对的是一大片泥泞的土地。FJ的屋子在平面坐标(0, 0)的位置，贝茜所在的牛棚则位于坐标(X,Y) (-500 <= X <= 500; -500 <= Y <= 500)处。当然咯， FJ也看到了地 …

1626: [Usaco2007 Dec]Building Roads 修建道路

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1362  Solved: 541 [Submit][Status][Discuss]

Description

Farmer John最近得到了一些新的农场，他想新修一些道路使得他的所有农场可以经过原有的或是新修的道路互达（也就是说，从任一个农场都可以经过一些首尾相连道路到达剩下的所有农场）。有些农场之间原本就有道路相连。 所有N(1 <= N <= 1,000)个农场（用1..N顺次编号）在地图上都表示为坐标为(X_i, Y_i)的点(0 …

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 507  Solved: 345 [Submit][Status][Discuss]

Description

    农夫约翰正驾驶一条小艇在牛勒比海上航行．

    海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一

1623: [Usaco2008 Open]Cow Cars 奶牛飞车

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 386  Solved: 266 [Submit][Status][Discuss]

Description

  编号为1到N的N只奶牛正各自驾着车打算在牛德比亚的高速公路上飞驰．高速公路有M(1≤M≤N)条车道．奶牛i有一个自己的车速上限Si(l≤Si≤1,000,000)．

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)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包．    帮助约翰找到最小的开销来满足需要，即采购到至 …