nyoj195 飞翔 dp

本文主要是介绍nyoj195 飞翔 dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目中map[i][j]可以穿越的意思就是map[i][j]到map[i+1][j+1]是一条可以从对角线穿越的特殊路径。
可知本题的最短路径就是穿过符合"条件"的尽可能多的特殊路径。该步骤可转化为求最长递增子序列。
而"条件"就是下一条可以穿过的特殊路径的i,j必须都大于上一条穿过的特殊路径的i,j(不能等于)。故要先进行排序。
然后用如果不穿过特殊路径的总路径(m+n)减去经过特殊路径减少的路程(2-sqrt(2))*maxx。最后乘上100。
 

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int dp[maxn],maxx;
struct node{int x,y;
}l[maxn];
bool cmp(node a,node b){if(a.x==b.x) return a.y<b.y;return a.x<b.x; 
}
int f(int k){maxx=-maxn;for(int i=1;i<=k;i++){dp[i]=1;for(int j=1;j<i;j++){if(l[i].x>l[j].x&&l[i].y>l[j].y&&dp[j]+1>dp[i]){dp[i]=dp[j]+1;maxx=max(maxx,dp[i]);}}}	return maxx;
}
int main(){int n,m;double s=sqrt(2);while(cin>>n>>m){int k;cin>>k;for(int i=1;i<=k;i++)cin>>l[i].x>>l[i].y;sort(l,l+k+1,cmp);int ans=(n+m-(2-s)*f(k))*100+0.5;//四舍五入cout<<ans<<endl;}
}        

 

这篇关于nyoj195 飞翔 dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---