nyoj 飛翔 195 （動态規劃++LIS變形）

飛翔

時間限制： 3000 ms  |           記憶體限制： 65535 KB 難度：4

描述

鷹最驕傲的就是翺翔，但是鷹們互相都很嫉妒别的鷹比自己飛的快，更嫉妒其他的鷹比自己飛行的有技巧。于是，他們決定舉辦一場比賽，比賽的地方将在一個迷宮之中。

這些鷹的起始點被設在一個N*M矩陣的左下角map[1，1]的左下角。終點被設定在矩陣的右上角map[N,M]的右上角，有些map[i,j]是可以從中間穿越的。每一個方格的邊長都是100米。如圖所示：

沒有障礙，也沒有死路。這樣設計主要是為了高速飛行的鷹們不要發現死路來不及調整而發生意外。潘帕斯雄鷹冒着減RP的危險從比賽承辦方戒備森嚴的基地中偷來了施工的地圖。但是問題也随之而來，他必須在比賽開始之前把地圖的每一條路都搞清楚，從中找到一條到達終點最近的路。（哈哈，笨鳥不先飛也要拿冠軍）但是此鷹是前無古鷹，後無來鷹的吃菜長大的鷹--菜鳥。他自己沒有辦法得出最短的路徑，于是緊急之下找到了學OI的你，希望找到你的幫助。

輸入

本題有多組資料。以EOF為輸入結束的标志。

每組測試資料的首行為n,m(0<n,m<=1000000),第2行為k（0<k<=1000）表示有多少個特殊的邊。以下k行為兩個數，i,j表示map[i,j]是可以直接穿越的。

輸出

僅一行，1，1-->n,m的最短路徑的長度，四舍五入保留到整數即可

樣例輸入

3 2      

3      

1 1      

3 2      

1 2      

樣例輸出

383      

AC代碼。。。      

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct zz
{
	int x;
	int y;
}q[11000];
int cmp(zz a,zz b)
{
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}
int b[1010];
int main()
{
	int n,m,t,i,j,k;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		scanf("%d",&t);
		for(i=0;i<t;i++)
			scanf("%d%d",&q[i].x,&q[i].y);
		sort(q,q+t,cmp);
		int max=0;
		memset(b,0,sizeof(b));
		for(i=0;i<t;i++)
		{
			b[i]=1;
			for(j=0;j<i;j++)
			{
				if(q[i].y>q[j].y&&q[i].x>q[j].x&&b[j]+1>b[i])
					b[i]=b[j]+1;
			}
			if(max<b[i])
				max=b[i];
		}
		printf("%.0lf\n",(m+n)*100-(2-sqrt(2))*max*100);
	}
	return 0;
}