大意：城市为正方形格子，每个格子的边长为100米。地铁站在其中一个十字路口。Nikanor从家里步行到地铁站。他沿着街道走，也可以穿越某一些格子的对角线，这样会近一些。 求Nikanor从西南角的家到东北角地铁站的最短路径。
input：
输入首行为N,M (0 < N,M <= 1000),东西、南北的格子数。Nikanor从格子（1，1）的西南角的家出发，地铁站位于格子（N，M）的东北角。第二行为K(0 <= K <= 100),表示有k个格子允许对角线穿越。以下K行为允许对角线穿越的格子，分别用一对数表示，空格隔开。
output：
求Nikanor的家到地铁站的最短路径，四舍五入到整数，单位：米。
input：
3 2
3
1 1
3 2
1 2
output：
383
分析：对于最多的步数就是N+M条边，为了尽量的少的路程，则应该尽量走那些斜边（勾股定理），则求出到达（N,M）的最多的斜边即可，这样变转换成了最长上升子序列。【参考程序】：
#include<iostream>
#include<cmath>
using namespace std;
struct node
{
int x,y;
}p[1100];
int opt[1100];
int n,m,k;
int cmp(const void *s,const void *t)
{
node i=*(node *)s,j=*(node *)t;
if (i.x!=j.x) return i.x-j.x;
else return i.y-j.y;
}
int main()
{
scanf("%d%d",&m,&n);
double sum=m+n;
scanf("%d",&k);
for (int i=0;i<k;i++)
scanf("%d%d",&p[i].x,&p[i].y);
qsort(p,k,sizeof(node),cmp);
memset(opt,0,sizeof(opt));
int ans=0;
for (int i=0;i<k;i++)
{
opt[i]=1;
for (int j=0;j<i;j++)
if (p[j].x<p[i].x && p[j].y<p[i].y)
if (opt[j]+1>opt[i])
opt[i]=opt[j]+1;
if (ans<opt[i]) ans=opt[i];
}
sum-=ans*2.0;//总的边(n+m)减去最多的斜边便是剩下的走的直边。
sum=(sum+sqrt(2.0)*ans*1.0)*100.0;
printf("%0.0lf\n",sum);
return 0;
}