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 (like …

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

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型男名誉起誓，他一定要在被流星砸到前，到达一个安全的地方 （也就是说，一块不会被任何流星砸到的土地）。如 …

题目链接 题意：有两跟柱子并排竖直放置，每根柱子有n个结点，从上往下标号1..n， 两根柱子间的结点间要连线，给出计划连接的情况。a[i]表示左边结点i连接右边结点a[i].但是要求连线不能交叉，所以计划可能不能全部执行。现在问最多能连接多少条线。 思路：由于不能交叉，而左边的结点是按照顺序给出的，所以右边连接的结点只能是越来越大。其实就是求a[i]的最长上升子序列。感觉算是LIS的一个比较巧妙的应用？ 由于n还是很大。所以必须nlogn的做法。 /* *********************************************** Author :111qqz Created Time :2016年04月01日 星期 …

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)的卡片。虽然 …