LIS

1207: [HNOI2004]打鼹鼠 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss]

# Time Limit: 5 Sec Memory Limit: 64 MB Submit: 667 Solved: 389 [Submit][Status][Discuss] Description # 贝茜是一只非常努力工作的奶牛，她总是专注于提高自己的产量。为了产更多的奶，她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时，标记为0..N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶，到结束时间为止。每次挤奶必须使用整个时间段。 但即使是贝茜也有她的产量限制。每次挤奶以后，她必须休息 R (1 ≤ R ≤ N) 个小时才能下次挤奶。给定Farmer John 计划的时间段，请你算出在 N 个小时内，最大的挤奶的量。

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

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1282 Solved: 766 [Submit][Status][Discuss]

首先回顾一下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 ans = max(ans,dp[i]); 12 } 然后我们发现，使得dp[i]得到同一个值的dp[j]可能有多个，那么选择哪个呢？ 假设 x<y<i，a[x]<a[y],dp[x]==dp[y]，那么我们选择x好还是y好呢？ 显然是x好。为什么？因为选择x潜力大。因为可能在x,y之间存在一个z,满足a[x]<a[z]<a[y],如果选择a[y]，就没有办法选择可能使长度更长的a[z]了。通俗得说。。我们要求的是最长上升子序列。。你一开始就弄那么大。。。后面还上哪上升去啊。。。长度小啊。。。