Problem Description:
In order to defend the enemy's missile attack, a country will develop a missile intercepting system. However, this missile intercept system has a defect: although its first shell can reach any height, each of the shells will not be higher than the previous height. One day, radar captures the enemy's missile. Since the system is still in the stage, there is only one system, so it is possible to intercept all missiles.
The height of the input missile is saved (the radar gives a high degree of data is not more than 30000 positive integers), calculating the maximum number of missiles can be intercepted by the system. If you want to intercept all missiles, you have to have the minimum of this missile system.
Sample:
INPUT: 389 207 155 300 299 170 158 65
OUTPUT: 6 (maximum number of intercepts)
2 (To intercept the number of systems to be equipped with all missiles)
Run example:
INPUT: 300 250 275 252 200 138 245
OUTPUT: 5 2
INPUT: 181 205 471 782 1033 1058 1111
OUTPUT: 1 7
Input: 465 978 486 324 575 384 278 214 657 218 445 123
OUTPUT: 6 4
Input: 236 865 858 565 545 445 455 656 844 735 638 652 569 714 845
OUTPUT: 6 7
problem analysis
The first question can be abstracted to ask for a set of number of largest sequences of the number. Setting ST (n) to the longest decrement sequence length in the array as the header. ST (N-1) = max (ST (x1), ST (x2) ... ST (xi)) 1. Where n <= xi <= n, and the number of XI in arrays is less than the nth 1 number. You can use recursive.
The second question: Store n heights with a chain table. First find the largest number in the list, and record the maximum number of next position T, delete the maximum number. Then start looking for the largest number from T, and then record it. Until T is the tail, end a round. The number of systems plus 1. Then start from the header to repeat the previous step until the linked list is empty. For example: 7 6 2 8 5 3 first find 8, delete 8. Go again from 5, 5 biggest deletion. Start from 3, 3 is deleted at the end, and end one round. Start with the head 7, the table is empty after deleting 7, 6, 2. Stop the system is: 8 5 3 and 7 6 2
The second questioning algorithm can be proven to have a tokenless figure.
data structure
The first question array stores N heights. Use the HIGH [] array in the program.
The second question with a single-link table with a lead node to store n numbers.
Typedef struct node
{
Int Val;
Struct Node * Next;
} Node, * link;
Program list
#include
#define n 100
INT high [N 1] = {0};
INT K = 0;
INT system = 0;
INT NomaxSQ (int N)
{
INT I, MAX;
IF (n == k)
Return 1;
Else
{
MAX = 0;
For (i = n 1; i <= k; i )
{
IF (high [i] MAX = NomaxSq (i); Break; } For (i = n 1; i <= k; i ) { IF (high [i] IF (NomaxSq (i)> max) MAX = NomaxSq (i); } Return Max 1; } } Typedef struct node { INT VAL; STRUCT NODE * NEXT } Node, * link; Node * priorelem (link l, node * t) { Node * p = L; While ((p! = 0) && (p-> next! = t))) P = P-> next; Return P; } void systemno () { INT I, MAX; Node * p, * t, * q; Node * MP, * TEMP; LINK L; L = (link) malloc (sizeof (node)); L-> Next = NULL; For (i = k; i> 0; - i) { P = (link) malloc (sizeof (node)); P-> Val = high [i]; P-> next = l-> next; l-> next = p; } DO { T = l-> next; DO { Q = priorelem (l, t); For (max = t-> val; t; q = t, t = t-> Next) IF (Max <= T-> VAL) { MAX = T-> VAL; Temp = T; MP = Q; } MP-> next = TEMP-> Next; Free (TEMP); T = mp-> next; WHILE (T); system; } while (l-> next); } Main () { Void systemno (); INT i = 0, n = 0; Int max; Char C; Char s [100]; While (c = getchar ())! = '/ n') { s [i ] = C; } s [i] = '/ 0'; i = 0; While (s [i]! = '/ 0') { IF (s [i] == '') i ; For (; s [i]> = '0' && s [i] <= '9'; i) n = 10 * n (s [i] - '0'); High [ k] = n; n = 0; } MAX = 0; For (i = 1; i <= k; i ) IF (Max MAX = NomaxSq (i); Printf ("% d", max); Systemno (); Printf ("% d", system); Getch (); }
