Pagini recente » Monitorul de evaluare | Profil victorl | Monitorul de evaluare | Diferente pentru blog/romanii-la-disneyworld-partea-intai intre reviziile 11 si 5 | Cod sursa (job #1330804)
#include <cstdio>
#define INF 0x3f3f3f3f
#define Nmax 5005
using namespace std;
int N,v[Nmax],DP[Nmax],daddy[Nmax];
int apartine[Nmax];
int ans = INF,pz;
int mini(int a,int b)
{
return a < b? a : b;
}
void Read()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i)
scanf("%d",v+i);
}
void Solve()
{
int minim;
for(int i = N ; i >= 1; --i)
{
DP[i] = INF;
minim = INF;
for(int j = i + 1; j <= N; ++j)
{
if(v[j] >= v[i])
apartine[j] = 1;
if(v[j] >= v[i] && v[j] < minim) /// aleg minimul mai mare ca v[i] ca
{ /// sigur e cel mai bun
minim = v[j];
if(DP[j] + 1 <= DP[i])
{
if(DP[j] + 1 < DP[i])
{
DP[i] = DP[j] + 1;
daddy[i] = j;
continue;
}
if(v[daddy[i]] > v[j])
daddy[i] = j;
}
}
}
if(DP[i] == INF)
{
DP[i] = 1;
daddy[i] = N + 1;
}
}
for(int i = 1; i <= N; ++i)
if(!apartine[i])
{
if(ans > DP[i]){
ans = DP[i];
pz = i;
}
else
if(ans == DP[i] && v[i] < v[pz])
pz = i;
}
}
void Print()
{
printf("%d\n",ans);
while(pz <= N)
{
printf("%d ",pz);
pz = daddy[pz];
}
}
int main()
{
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
Read();
Solve();
Print();
return 0;
}