mahmoud-a
8/27/2017 - 11:59 AM

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

``````#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;
}

``````