Pagini recente » Cod sursa (job #1532474) | simulareaii | Cod sursa (job #2407734) | Cod sursa (job #1259762) | Cod sursa (job #2238516)
#include <cstdio>
#define Nmax 5005
#define INF 1000010
using namespace std;
FILE *f=fopen("subsir2.in","r");
FILE *g=fopen("subsir2.out","w");
int v[Nmax],dp[Nmax],next[Nmax];
int n;
void citire()
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
}
void rezolva()
{
for(int i=n;i>=1;i--)
{
int val = INF;
int ind = 0;
for(int j=i+1;j<=n;j++)
if(v[j]<val && v[i] <= v[j])
{
if(ind == 0 || dp[j] <= dp[ind])
ind = j;
val = v[j];
}
next[i] = ind;
dp[i] = dp[ind] +1;
}
int val = v[1];
int ind = 1;
for(int i=2; i<=n; i++)
if(v[i]<val)
{
if(dp[i] <= dp[ind])
ind =i;
val = v[i];
}
fprintf(g,"%d\n",dp[ind]);
while(ind)
{
fprintf(g,"%d ",ind);
ind = next[ind];
}
}
int main()
{
citire();
rezolva();
return 0;
}