yangdong 2010-04-17 22:05:00
点我顶贴
收藏
删除
看数据范围就知道应该无视长宽，只找能够走的捷径数量的最大值，最后直接计算。
类似于贪吃什么的那题。
首先设有k个捷径、
按x值递增排列(因为每次走的捷径的x值必大于前面所有的)
再求最长递增子序列。
具体就是说:设f[i]表示前i个捷径所能产生的以第i个捷径为末端的递增序列的最大长度，y[i]表示第i个捷径的纵坐标。则该长度等于以j=1..i-1结尾的递增序列中满足y[j]小于y[i]的序列长度的最大值加1(即加上第i个)，得到状态转移方程
f[i]=max{f[j]+1}(1<=j<i且y[i]>y[j])，又知f[1]=1，递推、求max{f[1..i]}就行了。