Pagini recente » Cod sursa (job #1286747) | Cod sursa (job #1623803) | Cod sursa (job #2043934) | Cod sursa (job #2036355) | Cod sursa (job #94804)
Cod sursa(job #94804)
//100 puncte
using namespace std;
#define MAX_N 5005
#define INF 0x3f3f3f3f
#include <stdio.h>
FILE *fin=fopen("subsir2.in","r"),
*fout=fopen("subsir2.out","w");
int n,i,v[MAX_N];
int a[MAX_N],t[MAX_N];
//a[i] lungimea celui mai scurt subsir crescator maximal care incepe in i
//t[i] indicele termenului urmator lui i in subsirul care incepe in i - reconsituire
//complexitate n^2 - dinamica
void get_sequence(void)
{
int i,minvl=INF,min=INF,in=0;
for (i=1; i<=n; i++)
if (minvl>v[i])
{
if (a[i]==min)
if (v[i]<v[in]) in=i;
if (a[i]<min) { min=a[i]; in=i;}
minvl=v[i];
}
fprintf(fout,"%d\n",min);
fprintf(fout,"%d ",in);
while (t[in]!=0) {
fprintf(fout,"%d ",t[in]);
in=t[in];
}
fprintf(fout,"\n");
}
void solve(void)
{
int i,j,min,ai,minv;
a[n]=1; t[n]=0;
for (i=n-1; i>=1; i--)
{
min=INF; minv=INF; ai=INF;
for (j=i+1; j<=n; j++)
{
if (v[j]<min && v[j]>=v[i])
{
min=v[j];
if (ai==a[j])
if (v[j]<minv) { t[i]=j; minv=v[j];}
if (a[j]<ai)
{ ai=a[j]; t[i]=j; minv=v[j]; }
}
if ((v[j]<min) && (min!=INF) && (v[j]>=v[i]))
{
if (ai==a[j])
if (v[j]<minv) { t[i]=j; minv=v[j]; }
if (ai>a[j]) { t[i]=j; ai=a[j]; minv=v[j];}
}
}
if (ai!=INF) a[i]=ai+1; else { a[i]=1; t[i]=0; }
}
get_sequence();
}
int main()
{
fscanf(fin,"%d\n",&n);
for (i=1; i<=n; i++)
fscanf(fin,"%d",v+i);
solve();
fclose(fin);
fclose(fout);
return 0;
}