UVa: 497 - Strategic Defense Initiative

#include <iostream>
#include <sstream>
#include <stack>
#include <vector>

using namespace std;

string s;

int toInt()
{
    int n = 0;
    for(int i=0; i<s.size(); i++)
        n = n*10 + (s[i]-'0');
    return n;
}

int main()
{
    int tc;
    cin >> tc;

    ///Tengo que leer dos fines de línea
    getline(cin, s);
    getline(cin, s);
    for(int w=0; w<tc; w++)
    {
        int n = 0;
        vector <int> a;
        getline(cin, s);
        while(s.size())
        {
            a.push_back(toInt());
            getline(cin, s);
            n++;
        }
        vector <int> lis(n, 1);
        vector <int> from(n, -1);

        int p = 0; ///Posición final de LIS
        int m = 1; ///LIS
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(a[j] < a[i] && lis[i] < lis[j]+1)
                {
                    lis[i] = lis[j]+1;
                    from[i] = j;
                }
            }
            if(lis[i] > m)
            {
                m = lis[i];
                p = i;
            }
        }

        stack <int> r; ///Para mostrarlos invertidos

        if(w)
            cout << endl;
        cout << "Max hits: " << m << endl;
        r.push(a[p]);
        while(from[p] != -1)
        {
            r.push(a[from[p]]);
            p = from[p];
        }
        while(r.size())
        {
            cout << r.top() << endl;
            r.pop();
        }
    }
    return 0;
}