Pagini recente » Cod sursa (job #2829974) | Cod sursa (job #2572353) | Cod sursa (job #2964646) | Cod sursa (job #2496131) | Cod sursa (job #1521854)
/// dp[i] = cel mai scurt subsir maximal ce se termina pe pozitia i
#include <cstdio>
const int maxN = 5000;
const int inf = 1 << 20;
int N, v[maxN + 2], next[maxN + 2], dp[maxN + 2];
int main() {
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d", &N);
for(register int i = 1; i <= N; ++ i)
scanf("%d", &v[i]);
for(register int i = N; i > 0; -- i) {
int pos;
pos = next[i] = -1;
dp[i] = inf;
for(register int j = i + 1; j <= N; ++ j) {
if(v[i] <= v[j]) {
if(pos == -1 or v[pos] > v[j])
pos = j;
if(dp[i] > dp[pos] + 1 or (dp[i] == dp[pos] + 1 and v[pos] < v[next[i]])) { /// fac minim (inclusiv lexicografic)
dp[i] = dp[pos] + 1;
next[i] = pos;
}
}
}
if(dp[i] == inf)
dp[i] = 1;
}
int pos = 1; int Min = v[1];
for(register int i = 2; i <= N; ++ i) {
if(v[i] < Min) {
v[i] = Min;
if(dp[i] < dp[pos] or (dp[i] == dp[pos] and v[i] < v[pos]))
pos = i;
}
}
printf("%d\n", dp[pos]);
while(pos != -1) {
printf("%d ", pos);
pos = next[pos];
}
return 0;
}