Pagini recente » Cod sursa (job #698730) | Cod sursa (job #1762655) | Cod sursa (job #383940) | Monitorul de evaluare | Cod sursa (job #1330795)
#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,best,pzbest;
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)
{
minim = v[j];
/**int bad = 0;
for(int k = i + 1; k < j; ++k)
if(v[i] <= v[k] && v[k] <= v[j])
{
bad = 1;
break;
}
if(!bad)*/
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])
{
ans = mini(ans,DP[i]);
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;
}