BZOJ 1207: [HNOI2004]打鼹鼠 (LIS)

1207: [HNOI2004]打鼹鼠

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 2854  Solved: 1390
[Submit][Status][Discuss]

Description

鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

Input

第一行为n(n<=1000), m(m<=10000),其中m表示在这一段时间内出现的鼹鼠的个数,接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。

Output

仅包含一个正整数,表示被打死鼹鼠的最大数目

Sample Input

2 2
1 1 1
2 2 2

Sample Output

1

HINT

Source

 

思路:很巧妙的题目。类比LIS,如果两只仓鼠的曼哈顿距离小于等于两只仓鼠出现的时间,那么就可以从一只仓鼠转移到另一只仓鼠。利用这个条件,做二维的LIS即可。

 

BZOJ 1642: [Usaco2007 Nov]Milking Time 挤奶时间 (dp,类似LIS)

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 个小时内,最大的挤奶的量。

Input

1行三个整数NMR.接下来M行,每行三个整数SiEiPi

Output

 最大产奶量.

Sample Input

12 4 2
1 2 8
10 12 19
3 6 24
7 10 31

Sample Output

43

HINT

注意:结束时间不挤奶

 

思路:这题很像LIS啊。。由于每次结束要休息R的时间,所以把结束时间+R就好。

然后按照开始时间排序。

dp[i]表示前i个任务安排最大的挤奶量。

初始化dp[i] = a[i].val

转移的时候 dp[i] = max(dp[i],dp[j]+a[i].val)  (j<i&&a[j].r<=a[i].l)

 

 

 

hdu 1950 Bridging signals (LIS)

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

 

 

BZOJ 1609: [Usaco2008 Feb]Eating Together麻烦的聚餐(LIS nlogn解法)

 

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(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来,卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后,FJ找到了一种简单些的方法:奶牛们不动,他沿着队伍从头到尾走一遍把那些他认为排错队的奶牛卡片上的编号改掉,最终得到一个他想要的每个组中的奶牛都站在一起的队列,例如111222333或者333222111。哦,你也发现了,FJ不反对一条前后颠倒的队列,那样他可以让所有奶牛向后转,然后按正常顺序进入餐厅。 你也晓得,FJ是个很懒的人。他想知道,如果他想达到目的,那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候,都不会挪位置。

Input

第1行: 1个整数:N 第2..N+1行: 第i+1行是1个整数,为第i头奶牛的用餐批次D_i

Output

第1行: 输出1个整数,为FJ最少要改几头奶牛卡片上的编号,才能让编号变成他设想中的样子

Sample Input

5
1
3
2
1
1
输入说明:
队列中共有5头奶牛,第1头以及最后2头奶牛被设定为第一批用餐,第2头奶牛的预设是第三批用餐,第3头则为第二批用餐。

Sample Output

1

输出说明:

如果FJ想把当前队列改成一个不下降序列,他至少要改2头奶牛的编号,一种可行的方案是:把队伍中2头编号不是1的奶牛的编号都改成1。不过,如果FJ选择把第1头奶牛的编号改成3就能把奶牛们的队伍改造成一个合法的不上升序列了。

 

思路:先考虑一个方向。最后要排列成一个不下降子序列。
需要修改的最少次数就是总长度减去最长的不下降子序列的长度。
所以问题就变成了最长求不下降子序列的长度。
由于n最大30000,O(n^2)的复杂度会TLE.所以去学了下nlogn的做法LIS nlogn解法讲解
然后再反正做一遍,求最小值即可。
以及:原来upper_bound和lower_bound可以对数组直接用啊。。。
以及:原来reverse也可以对数组用啊。。。。

最长上升子序列nlogn解法

首先回顾一下n^2的做法。
状态转移方程为dp[i] =max(1,dp[j]) (1=<j<=i-1&&a[i]>a[j])

然后我们发现,使得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]了。通俗得说。。我们要求的是最长上升子序列。。你一开始就弄那么大。。。后面还上哪上升去啊。。。长度小啊。。。

因此我们得出一个结论,对于dp[t]==k的所有t,要选择a[t]最小的,这样有更大可能得到更长的序列。

我们用g[k]表示所有dp[t]==k的t中,最小的a[t]的值。g[k] = min{A[t]} (dp[t] = k)

我们可以发现关于g的两个性质。

(1) g[k]肯定是单调不增的。因为求最小值嘛,肯

(2)g[1]<g[2]<g[3]….g数组是单调递增的。其实也很好理解,因为是求最长上升子序列,长度为i的序列的最末尾元素肯定要比长度为i+1的末尾的元素小,不然还怎么上升。

g数组初始为无穷大,g[i]表示还没有dp[t]==i的值。

 

1. 设当前已求出的最长上升子序列的长度为len(初始时为1),每次读入一个新元素x:

2. 若x>d[len],则直接加入到d的末尾,且len++;(利用性质2)

   否则,在g中二分查找,找到第一个比x小的数g[k],并g[k+1]=x,在这里x<=g[k+1]一定成立(性质1,2)

上面这段引用并没有很懂。。。。。回头再看。

 

 

 

模板如下。