Pagini recente » Atasamentele paginii denisilie94 | Cod sursa (job #1719573) | Cod sursa (job #1212680) | Cod sursa (job #2869867) | Cod sursa (job #473300)
Cod sursa(job #473300)
#include <cstdio>
#define file_in "subsir2.in"
#define file_out "subsir2.out"
#define nmax 6050
int n;
int a[nmax];
int v[nmax];
int t[nmax];
void citire(){
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;++i)
scanf("%d", &v[i]);
}
void solve(){
int i,j,poz,p,rez,min;
//A[i] = lungimea celui mai scurt subsir crescator maximal care incepe cu pozitia i
//T[i] = urmatorul element dupa pozitia i in cel mai scurt subsir crescator maximal
// care incepe cu i (pentru reconstiutire)
a[n]=1;
t[n]=n;
for (i=n-1;i>=1;--i)
{
a[i]=0x3f3f3f3f;
poz=0x3f3f3f3f;
for (j=i+1;j<=n;++j)
{
if (v[i]<=v[j] && a[i]>=a[j]+1 && poz>v[j])
a[i]=a[j]+1,
t[i]=j;
if (poz>=v[j] && v[j]>=v[i])
poz=v[j];
}
if (a[i]==0x3f3f3f3f)
a[i]=1,
t[i]=i;
}
p=0;
min=0x3f3f3f3f;
rez=0x3f3f3f3f;
v[p]=0x3f3f3f3f;
for (i=1;i<=n;++i)
{
if ((a[i]<rez || (a[i]==rez && v[i]<v[p])) && v[i]<min)
rez=a[i],
p=i;
if (v[i]<min)
min=v[i];
}
printf("%d\n", rez);
while(t[p]!=p)
{
printf("%d ", p);
p=t[p];
}
printf("%d", p);
}
int main()
{
citire();
solve();
fclose(stdin);
fclose(stdout);
return 0;
}