Pagini recente » Cod sursa (job #1697288) | Cod sursa (job #370990) | Cod sursa (job #2387403) | Cod sursa (job #811486) | Cod sursa (job #92536)
Cod sursa(job #92536)
//infoarena subsir2
// http://infoarena.ro/problema/subsir2
//O(n^2)
#include <cstdio>
#include <cstdlib>
#define INF 0x7FFFFFFF
#define min(a,b) ((a) < (b) ? (a) : (b))
#define max(a,b) ((a) > (b) ? (a) : (b))
using namespace std;
#define MAX 5000
int v[MAX], N, Lmin, L[MAX], T[MAX],rez[MAX];
void calc()
{
L[N-1] = 1;
T[N-1] = N-1;
for (int i = N-2; i>=0; i--)
{
int vmin = INF, l = INF, poz=INF;
for (int j = i+1; j<N; j++)
{
if (v[j] >= v[i] && v[j] < vmin && L[j] <= l)
{
l = L[j];
if ( poz == INF )
poz = j;
else
if ( L[j] == l && v[j] <= v[poz] )
poz = j;
};
if (v[j] >=v[i] && v[j] <vmin) vmin = v[j];
};
if (l==INF) { l =0; poz = i; };
L[i] = l + 1;
T[i] = poz;
};
};
void refa(int poz, int &nr)
{
for ( int i = poz; ; i = T[i])
{
rez[nr++] = i;
if (T[i] == i ) break;
};
};
int check(int nr)
{
for (int i =0; i<rez[0]; i++)
if (v[i] <= v[rez[0]])
return 0;
for (int i = rez[nr-1]+1; i<N; i++)
if (v[i] >= v[rez[nr-1]])
return 0;
for (int i = 1 ; i<nr; i++)
for (int j = rez[i-1]+1; j<rez[i]; j++)
if (v[j] >= v[rez[i-1]] && v[j] <= v[rez[i]])
return 0;
return 1;
};
int main()
{
freopen("subsir2.in", "r", stdin);
freopen("subsir2.out", "w", stdout);
scanf("%d\n", &N);
for (int i = 0; i<N; i++)
scanf("%d", &v[i]);
calc();
int vmin,k=0,poz1=0, poz2;
Lmin = L[0]; vmin = v[0];
for (int i=1; i<N; i++)
{
if (v[i] < vmin ) vmin = v[i]+k;
else if (v[i] == vmin) { vmin++; k =1; };
if (v[i] == vmin && L[i] <= Lmin)
{
Lmin = L[i];
poz1 = i;
};
};
poz2=0;
for (int i = 1; i<N; i++)
if (L[i] == Lmin && v[i] < v[poz2])
poz2 = i;
int nr=0;
refa(poz2,nr);
if (nr != Lmin || !check(nr))
{
nr=0;
refa(poz1,nr);
};
printf("%d\n", Lmin);
for (int i = 0; i<nr; i++)
printf("%d ", rez[i]+1);
fclose(stdin);
fclose(stdout);
return 0;
};