Pagini recente » Istoria paginii utilizator/sanke | Monitorul de evaluare | Istoria paginii utilizator/energizerbunny | Monitorul de evaluare | Cod sursa (job #1330778)
#include <cstdio>
#define INF 0x3f3f3f3f
#define Nmax 5005
using namespace std;
int N,v[Nmax],DP[Nmax],daddy[Nmax];
int apartine[Nmax];
int ans = 999999,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()
{
for(int i = N ; i >= 1; --i)
{
DP[i] = INF;
for(int j = i + 1; j <= N; ++j)
if(v[j] >= v[i])
{
apartine[j] = 1;
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;
}