本文主要是介绍飞翔（最长单调递增子序列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;typedef struct node
{int x,y;
}node;bool cmp(node a,node b)
{if(a.x==b.x) //这里必须要这样排return a.y<b.y;return a.x<b.x;
}node p[1005];
int dp[1005];int main()
{int n,m,k,i,j,sum;while(cin>>n>>m){memset(dp,0,sizeof(dp));cin>>k;for(i=0;i<k;i++)cin>>p[i].x>>p[i].y;sort(p,p+k,cmp);for(i=0;i<k;i++){for(j=i+1;j<k;j++)//p[j].x>p[i].x，在x轴上也有递增特性if(p[j].x>p[i].x && p[j].y>p[i].y && dp[i]+1>dp[j])dp[j]=dp[i]+1;}sort(dp,dp+k); //原先这里忘了排序，一直导致WA。。。。。sum=dp[k-1]+1; //一共走了sum条特殊边(最长单调递增子序列的长度)double ans=(m+n-(sum*(2-sqrt(2))))*100; //每走一条特殊边就少走2-sqrt(2)if(ans-int(ans)>=0.5)cout<<(int)ans+1<<endl;elsecout<<(int)ans<<endl;}return 0;
}
总结：思路就是尽量多的走特殊路段，所以就是求所有特殊路段的最长单调递增子序列，但要注意的是同时求两个方向上的最长单调递增子序列，说的直接一点就是老鹰走特殊路段是斜着飞的，即（x,y）都加一
这篇关于飞翔（最长单调递增子序列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
