Pagini recente » Cod sursa (job #2834731) | Cod sursa (job #1770656) | Cod sursa (job #730312) | Cod sursa (job #248735) | Cod sursa (job #486607)
Cod sursa(job #486607)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char InFile[]="subsir2.in";
const char OutFile[]="subsir2.out";
const int MaxN=5010;
ifstream fin(InFile);
ofstream fout(OutFile);
int v[MaxN],best[MaxN],p[MaxN],n,sol,soli,vmin;
vector<int> ind;
vector<int> ind1,ind2;
int main()
{
v[0]=-1000010;
best[0]=0;
p[0]=0;
fin>>n;
for(register int i=1;i<=n;++i)
{
fin>>v[i];
vmin=-1000010;
for(register int j=0;j<i;++j)
{
if(v[j]<v[i])
{
if(best[i]<best[j])
{
best[i]=best[j];
p[i]=j;
vmin=v[j];
}
else if(best[i]==best[j] && vmin>v[j])
{
vmin=v[j];
p[i]=j;
}
}
}
++best[i];
}
fin.close();
sol=0;
for(register int i=0;i<=n;++i)
{
if(best[i]>sol)
{
sol=best[i];
soli=i;
}
else if(best[i]==sol)
{
bool better=true;
int t1=soli,t2=i;
while(t1 && t2)
{
ind1.push_back(t1);
ind2.push_back(t2);
t1=p[t1];
t2=p[t2];
}
for(register int j=(int)ind1.size()-1;j>=0;--j)
{
if(v[ind1[j]]<v[ind1[j]])
{
break;
}
else if(v[ind1[j]]>v[ind1[j]])
{
better=false;
break;
}
}
if(better)
{
soli=i;
}
ind1.clear();
ind2.clear();
}
}
while(soli)
{
ind.push_back(soli);
soli=p[soli];
}
sort(ind.begin(),ind.end());
fout<<sol<<"\n";
for(register int i=0;i<(int)ind.size();++i)
{
fout<<ind[i]<<" ";
}
fout.close();
return 0;
}