Pagini recente » Cod sursa (job #2753124) | Cod sursa (job #1682114) | Cod sursa (job #2865638) | Cod sursa (job #1816568) | Cod sursa (job #1696555)
#include <cstdio>
#define NMAX 5000
#define INF 1000001
using namespace std;
int v[NMAX + 1],dm[NMAX + 1],next[NMAX + 1]; /// lista simplu inlantuita
/// dm = cel mai scurt subsir maximal ce se termina pe poz i
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int n,i,poz,min,j;
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d",&v[i]);
for (i=n;i>=1;i--){
poz = next[i] = -1;
dm[i] = INF;
for (j=i+1;j<=n;j++){
if (v[i] <= v[j]){
if (poz == -1 || v[poz] > v[j])
poz = j;
if (dm[i] > dm[poz] + 1 || (dm[i] == dm[poz] + 1 && v[poz] < v[next[i]])){
dm[i] = dm[poz] + 1;
next[i] = poz;
}
}
}
if (dm[i] == INF)
dm[i] = 1;
}
poz = 1;
min = v[1];
for (i=2;i<=n;i++){
if (v[i] < min){
min = v[i];
if (dm[i] < dm[poz] || (dm[i] == dm[poz] && v[i] < v[poz]))
poz = i;
}
}
printf("%d\n",dm[poz]);
while (poz != -1){
printf("%d ",poz);
poz = next[poz];
}
return 0;
}