【航线设置动态规划】

 1 // Project name : 航线设置
 2 // File name    : main.cpp
 3 // Author       : Izumu
 4 // Date & Time  : Sun Jul 15 16:33:54 2012
 5 
 6 
 7 #include <iostream>
 8 #include <stdio.h>
 9 #include <string>
10 #include <cmath>
11 #include <algorithm>
12 using namespace std;
13 
14 #define MAXN 1010
15 
16 struct FriendCity
17 {
18     int a, b;
19 };
20 
21 bool cmp(FriendCity fa, FriendCity fb)
22 {
23     if (fa.a < fb.a)
24     {
25         return true;
26     }
27     else
28     {
29         return false;
30     }
31 }
32 
33 FriendCity map[MAXN];
34 
35 int reg[MAXN];
36 
37 int n;
38 
39 void init()
40 {
41     for (int i = 1; i <= n; i++)
42     {
43         cin >> map[i].a >> map[i].b;
44     }
45 
46     sort(map + 1, map + n + 1, cmp);
47 }
48 
49 void dp()
50 {
51     reg[1] = 1;
52     for (int i = 2; i <= n; i++)
53     {
54         int max = 0;
55         for (int j = 1; j < i; j++)
56         {
57             if (map[j].b < map[i].b && max < reg[j])
58             {
59                 max = reg[j];
60             }
61         }
62         reg[i] = max + 1;
63     }
64 }
65 
66 int getResult()
67 {
68     int max_tmp = reg[1];
69     for (int i = 2; i <= n; i++)
70     {
71         if (reg[i] > max_tmp)
72         {
73             max_tmp = reg[i];
74         }
75     }
76     return max_tmp;
77 }
78 
79 
80 int main()
81 {
82     int time = 0;
83     while (cin >> n)
84     {
85 
86         time++;
87         init();
88         dp();
89         cout << "Case " << time << ":" << endl;
90         cout << "The Maximal number is: " << getResult() <<endl;
91     }
92     return 0;
93 }
94 
95 // end 
96 // ism
【航线设置 动态规划】

【航线设置动态规划】
