学步园

参考POJ 2533, 1836, 1887

下面附1887代码，

#include <iostream><br /> #include <algorithm><br /> using namespace std;<br /> int N;<br /> int data[100001];<br /> int maxLen[100001];<br /> void compute(int c)<br /> {<br /> maxLen[N] = 1;<br /> for(int i = N - 1; i >= 1; i--)<br /> {<br /> int max = 0;<br /> for(int j = N; j > i; j--)<br /> {<br /> if (data[i] > data[j])<br /> {<br /> if(maxLen[j] > max)<br /> {<br /> max = maxLen[j];<br /> }<br /> }<br /> }<br /> maxLen[i] = max + 1;<br /> }<br /> cout << "Test #" << c << ":" << endl;<br /> cout << " maximum possible interceptions: " <<<br /> *max_element(maxLen + 1, maxLen + N + 1) << endl;<br /> cout << endl;<br /> }<br /> int main()<br /> {<br /> int n;<br /> int c = 0;<br /> cin >> n;<br /> while(n != -1)<br /> {<br /> int index = 0;<br /> while(n!= -1)<br /> {<br /> data[++index] = n;<br /> cin >> n;<br /> }<br /> N = index;<br /> c++;<br /> compute(c);<br /> cin >> n;<br /> }<br /> }