Pagini recente » Cod sursa (job #2005544) | Profil M@2Te4i | Profil Decoy121 | Solutii preONI 2006, Runda finala | Cod sursa (job #2022796)
#include <fstream>
#include <vector>
#include <queue>
#define VAL 5005
#define INF 1000000000
using namespace std;
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
int N, i, j, mn, mx, v[VAL];
int dp[VAL], prec[VAL], poz;
bool okb[VAL], oke[VAL];
vector <int> G[VAL], SOL;
queue <int> Q;
void BFS(int nod)
{
int i;
dp[nod]=1;
Q.push(nod);
while (Q.empty()==false)
{
nod=Q.front();
Q.pop();
for (i=G[nod].size()-1; i>=0; i--)
{
if (dp[G[nod][i]]>dp[nod]+1)
{
dp[G[nod][i]]=dp[nod]+1;
Q.push(G[nod][i]);
prec[G[nod][i]]=nod;
}
}
}
}
bool Check(int a, int b)
{
for (int i=0; i<G[a].size(); i++)
if (G[a][i]==b)
return true;
return false;
}
int main()
{
fin >> N;
mn=INF;
for (i=1; i<=N; i++)
{
fin >> v[i];
dp[i]=INF;
if (v[i]<mn)
{
mn=v[i];
okb[i]=true;
}
}
mx=-INF;
for (i=N; i>=1; i--)
{
mn=INF;
for (j=i+1; j<=N; j++)
{
if (v[j]>=v[i] && mn>v[j])
{
mn=v[j];
G[i].push_back(j);
}
}
if (v[i]>mx)
{
mx=v[i];
oke[i]=true;
}
}
for (i=N; i>=1; i--)
if (okb[i]==true)
BFS(i);
mn=INF;
for (i=N; i>=1; i--)
{
if (oke[i]==true && mn>dp[i])
{
mn=dp[i];
poz=i;
}
}
fout << mn << '\n';
mn--;
SOL.push_back(poz);
for (i=poz-1; i>0; i--)
{
if (dp[i]==mn && Check(i, poz)==true)
{
poz=i;
SOL.push_back(i);
mn--;
if (mn==0)
break;
}
}
for (i=SOL.size()-1; i>=0; i--)
fout << SOL[i] << " ";
fin.close();
fout.close();
return 0;
}