Pagini recente » Cod sursa (job #3277784) | Cod sursa (job #2760138) | Cod sursa (job #2975877) | Cod sursa (job #1002322) | Cod sursa (job #487188)
Cod sursa(job #487188)
#include<fstream>
#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
#define MAXN 5008
const int oo=0x3f3f;
int main()
{
int n,x,sol=0x3f3f,psol=0;
fstream fin("subsir2.in", fstream::in);
fstream fout("subsir2.out", fstream::out);
vector<int> v,bst,pred;
bitset<MAXN> candidate;
fin>>n;
//cout<<n<<endl;
bst.resize(n);
pred.resize(n);
for(int i=0, min=oo; i<n; ++i)
{
fin>>x;
v.push_back(x);
if(x<min)
{
min=x;
candidate[i]=true;
}
}
/*for(int i=0; i<n; ++i)
{
cout<<v[i]<<" ";
}
cout<<endl;*/
for(int i=n-1; i>=0; --i)
{
int min=oo;
bst[i]=oo;
pred[i]=i;
for(int j=i+1; j<n; ++j)
{
if(v[i]<=v[j])
{
if(v[j]<min)
{
if(bst[i]>bst[j]+1 || (bst[i]==bst[j]+1 && v[j]<v[pred[i]]))
{
bst[i]=bst[j]+1;
pred[i]=j;
}
min=v[j];
}
}
}
if(bst[i]==oo)
{
bst[i]=1;
}
if(candidate[i])
{
if(bst[i]<sol || (bst[i]==sol && v[i]<v[psol]))
{
sol=bst[i];
psol=i;
}
}
}
fout<<sol<<endl;
fout<<psol+1<<" ";
while(psol!=pred[psol])
{
psol=pred[psol];
fout<<psol+1<<" ";
}
fout<<endl;
fin.close();
fout.close();
return 0;
}