Pagini recente » Cod sursa (job #1980312) | Cod sursa (job #3181894) | Cod sursa (job #404604) | Cod sursa (job #2858067) | Cod sursa (job #495472)
Cod sursa(job #495472)
// infoarena: problema/subsir2 //
#include <fstream>
#define MAXN 5010
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
int x[MAXN],i,j,s[MAXN],k[MAXN],m,n,l,p,q,r[MAXN],minim;
bool ok[MAXN];
int main()
{
in>>n;
minim = 1<<29;
for(i=1; i<=n; i++)
{
in>>x[i];
if(minim > x[i])
{
ok[i] = 1;
minim = x[i];
}
}
s[n] = 1; k[n] = n;
for(i=n; i>=1; i--)
{
m = 0;minim = 1<<29;s[i] = 1<<29;
for(j=i+1; j<=n; j++)
if(x[j] >= x[i] && x[j] < minim)
{
if(s[i] > s[j] + 1 || (s[i] == s[j] +1 && x[j] < x[k[i]]))
s[i] = s[j] + 1, k[i] = j;
minim = x[j];
}
if(s[i] == 1<<29)
s[i] = 1, k[i] = i;
if(ok[i] && (s[q] < s[i] || s[q] == s[i] && x[q] > x[i]))
q = i;
}
out<<s[q]<<'\n';
p = q;
while(p != k[p])
{
out<<p<<' ';
r[++r[0]] = p;
p = k[p];
}
out<<p;
/*
for(i=r[0]; i>=1; --i)
out<<r[i]<<' ';
*/
return 0;
}