https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=438

497 - Strategic Defense Initiative.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

int n;
const int MAX = 1e4+5;
const int OO = 1e9;

int a[MAX];
int cache[MAX][MAX];

int maxHits(int i, int pre) {
    if(i == n)
        return 0;
    int &ret = cache[i][pre];
    if(ret != -1)
        return ret;
    int ch1 = -1*OO;
    if(a[i] > a[pre]) {
        ch1 = 1+maxHits(i+1, i);
    }
    int ch2 = maxHits(i+1, pre);

    return ret = max(ch1, ch2);
}

void traceOperations(int i, int pre) {
    if(i == n)
        return;

    int ch1 = -1*OO;
    if(a[i] > a[pre]) {
        ch1 = 1+maxHits(i+1, i);
    }
    int ch2 = maxHits(i+1, pre);

    int opt = maxHits(i, pre);

    if(opt == ch1) {
        cout << a[i] << endl;
        traceOperations(i+1, i);
    } else {
        traceOperations(i+1, pre);
    }

    return;

}

int main() {
    int t;
    cin>>t;
    int tmp = t;
    while(t--) {
        int x;
        n = 0;
        clr(cache, -1);
        clr(a, -1);
        string s, foo;
        if(t == tmp-1) {
            getline(cin, foo);
            getline(cin, foo);
        }
        while(getline(cin, s) && s!="") {
            istringstream iss(s);
            iss>>x;
            a[n] = x;
            //cout <<"DEBUG : "<< a[n] <<endl;
            n++;
        }
        cout << "Max hits: "<< maxHits(0, n) << endl;
        traceOperations(0, n);
        if(t!=0)
            cout << endl;
    }
    return 0;
}