Pagini recente » Cod sursa (job #2113548) | Cod sursa (job #2490020) | Cod sursa (job #2494917) | Cod sursa (job #378099) | Cod sursa (job #2265822)
#include <bits/stdc++.h>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
const int NMAX = 5005;
const int VALMAX = 1000001;
int v[NMAX], dp[NMAX], minpref[NMAX], reconst[NMAX];
struct Data {
int x, y;
bool operator< (Data other) const {
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
int main() {
int n;
in >> n;
minpref[0] = VALMAX;
for(int i = 1; i <= n; i ++) {
in >> v[i];
minpref[i] = min(v[i], minpref[i - 1]);
}
int scmax = NMAX, start;
for(int i = n; i >= 1; i --) {
int currmin = VALMAX, currmax = -VALMAX;
dp[i] = NMAX;
for(int j = i + 1; j <= n; j ++)
if(v[j] >= v[i] && currmin > v[j]) { /// aici conditia de ok
if(dp[i] == dp[j] + 1 && v[reconst[i]] > v[j])
reconst[i] = j;
if(dp[i] > dp[j] + 1) {
dp[i] = dp[j] + 1;
reconst[i] = j;
}
if(v[j] >= v[i])
currmin = min(currmin, v[j]);
}
if(dp[i] == NMAX)
dp[i] = 1;
if(scmax > dp[i] && minpref[i - 1] > v[i]) {
scmax = dp[i];
start = i;
}
if(scmax == dp[i] && minpref[i - 1] > v[i] && v[i] < v[start])
start = i;
//cout << i << " " << dp[i] << " " << (minpref[i - 1] > v[i]) << endl;
}
out << scmax << "\n";
while(start) {
out << start << " ";
start = reconst[start];
}
return 0;
}