Pagini recente » Cod sursa (job #496193) | Cod sursa (job #777398) | Cod sursa (job #3164481) | Cod sursa (job #1316108) | Cod sursa (job #570805)
Cod sursa(job #570805)
#include<fstream>
#define dmax 5003
#define mult 1000001
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int n,x[dmax],y[dmax],k[dmax], mn, lmn;
bool b[dmax];
int main()
{
int i,j,ok,t;
in>>n;
for(i=1;i<=n;i++)
in>>x[i];
in.close();
lmn = mult;
for(i=n;i>=1;i--)
{
mn = mult;
ok = 1;
mn = mult;
for(j=i+1; j<=n; j++)
if(x[j] >= x[i])
{
if(x[j] <= mn)
{
mn = x[j];
if(y[i] == 0)
{ y[i] = y[j]+1;
k[i] = j;
}
else if(y[i] > y[j]+1)
{
y[i] = y[j]+1;
k[i] = j;
}
else if(y[i] == y[j]+1)
{
if(x[j] < x[k[i]] || k[i]==0)
k[i] = j;
}
b[j]=1;
}
}
}
for(i=1;i<=n;i++)
if(y[i] < lmn && !b[i])
lmn = y[i];
t = -1;
for(i=1;i<=n;i++)
if(y[i] == lmn)
if(x[i] < x[t] || t ==-1)
t = i;
out<<lmn+1<<'\n';
while(t)
{ out<<t<<" ";
t = k[t];
}
out.close();
return 0;
}