UVA Solution 497 – Strategic Defense Initiative – Solution in C,C++

UVA Onilne Judge Solution UVA-Volume 4

UVA Solution 497 – Strategic Defense Initiative – Solution in C,C++ – Volume 4

UVA Online Judge Solution 497 – Strategic Defense Initiative | Volume 4
UVA Problem Link -497 – Strategic Defense Initiative

Problem Name: 497 – Strategic Defense Initiative
Problem Number : UVA – 497 – Strategic Defense Initiative
Online Judge : UVA Online Judge Solution
Volume: 4
Solution Language : C plus plus

UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list

UVA Solution 497 – Strategic Defense Initiative Code in CPP:

#include <stdio.h>
#include <string.h>

struct
LIS {
int
A[1000], n, maxLIS;
int
pos[1000], lis[1000];
void
findLIS() {
int
i, l, m, r, newSet;
maxLIS = -1;
for
(i = 0; i < n; i++) {
l = 0, r = maxLIS, newSet = -1;
while
(l <= r) {
m = (l+r)/2;
if
(pos[m] <= A[i]) {
if
(m == maxLIS || pos[m+1] > A[i]) {
newSet = m+1;
break
;
}
else
l = m+1;
}
else
r = m-1;
}

if
(newSet == -1)
newSet = 0;
pos[newSet] = A[i];
lis[i] = newSet+1;
if
(maxLIS < newSet)
maxLIS = newSet;
}

maxLIS++;
}

void
printLIS() {
int
ans[1000], at = 0, i, tmp = maxLIS;
for
(i = n-1; i >= 0; i--) {
if
(lis[i] == tmp)
tmp--, ans[at++] = A[i];
}

for
(i = at-1; i >= 0; i--)
printf("%dn", ans[i]);
}
};

int
main() {
int
t, n;
char
str[100];
LIS data;
scanf("%d", &t);
getchar();
getchar();
while
(t--) {
n = 0;
while
(gets(str)) {
if
(str[0] == '')
break
;
sscanf(str, "%d", &data.A[n]);
n++;
}

data.n = n;
data.findLIS();
printf("Max hits: %dn", data.maxLIS);
data.printLIS();
if
(t)
puts("");
}

return
0;
}

Tags: UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list, UVA 497  code in C, UVA 497  code in C++, UVA 497 – Strategic Defense Initiative solution in C, UVA 497 solution

Leave a Reply

Your email address will not be published.