南阳195----飞翔

 1 /*
 2 1、入手点为k（<=1000）
 3 2、逆序dp，保证最佳路径
 4 */
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<cmath>
 8 #include<algorithm>
 9 using namespace std;
10 typedef struct
11 {
12     int x,y;
13 } cus;
14 
15 cus a[1005];
16 int d[1005];
17 
18 int cmp(cus p1,cus p2)
19 {
20     if(p1.x == p2.x)
21         return p1.y < p2.y;
22     return p1.x < p2.x;
23 }
24 
25 int solven(int t)
26 {
27     int ans=0;
28     int i,j;
29     for(i=t-2; i>=0; --i)
30     {
31         for(j=i+1; j<t; ++j)
32             if(a[i].x<a[j].x && a[i].y<a[j].y && d[i]<d[j]+1)
33                 d[i] = d[j] + 1;
34         if(ans < d[i])
35             ans = d[i];
36     }
37     return ans;
38 }
39 
40 int main()
41 {
42     int i,t,n,m;
43     double ans;
44     while(scanf("%d%d",&n,&m) != EOF)
45     {
46         scanf("%d",&t);
47         for(i=0; i<t; ++i)
48         {
49             scanf("%d%d",&a[i].x,&a[i].y);
50             d[i] = 1;
51         }
52         sort(a,a+t,cmp);
53         t = solven(t);
54         ans = (n + m - 2*t + t*sqrt(2.0))*100.0;
55         printf("%.lf
",ans);
56     }
57     return 0;
58 }