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 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