水题一道!
1 #include <iostream>
2 #include <vector>
3 #include <new>
4 using namespace std;
5
6 struct nod {
7 int num;
8 int max_num;
9 };
10
11 int m = 1;
12
13 void ji_suan( vector<nod *> &v2 )
14 {
15 int max = 1;
16 for ( vector<nod *> ::iterator p = v2.begin(),q = v2.end(); p != q; ++p )
17 {
18 for ( vector <nod *> ::iterator p1 = p + 1; p1 != q; ++p1 )
19 {
20 if ( (*p)->num > (*p1)->num )
21 {
22 if ( (*p)->max_num + 1 > (*p1)->max_num )
23 {
24 (*p1)->max_num = (*p)->max_num + 1;
25 if ( max < (*p1)->max_num )
26 max = (*p1)->max_num;
27 }
28 }
29 }
30 }
31 printf ( "Test #%d:\n",m++ );
32 cout << " maximum possible interceptions: " << max << endl;
33 }
34
35 int main()
36 {
37 //freopen( "in.txt","r",stdin );
38 vector<nod *> v1;
39 int num;
40 while ( cin >> num && num != -1 )
41 {
42 int n;
43 nod *p = new nod;
44 p->max_num = 1;
45 p->num = num;
46 v1.push_back(p);
47 while ( cin >> n && n != -1 )
48 {
49 p = new nod;
50 p->num = n;
51 p->max_num = 1;
52 v1.push_back(p);
53 }
54 ji_suan( v1 );
55 v1.clear();
56 cout << endl;
57 }
58 return 0;
59 }