Pagini recente » Cod sursa (job #1530875) | Cod sursa (job #2040638) | Cod sursa (job #1698968) | Cod sursa (job #415547) | Cod sursa (job #574782)
Cod sursa(job #574782)
// infoarena: problema/subsir2 //
#include <fstream>
using namespace std;
ifstream in("subsir2.in");
ofstream out("subsir2.out");
const int MAXN = 5010;
int l[MAXN],r[MAXN],x[MAXN],i,j,n,m,mi,mr;
int main()
{
in>>n;
for(i=1; i<=n; i++)
in>>x[i], r[i] = l[i] = 1;
l[1] = 1;
for(i=2; i<=n; i++)
for(j=1; j<i; j++)
if(x[j] <= x[i] && (l[i] == 0 || l[i]<l[j]+1))
l[i] = l[j]+1;
r[n] = 1;
for(i=n-1; i>=1; i--)
for(j=i+1; j<=n; j++)
if(x[i] <= x[j] && (r[i] == 0 || r[i]<r[j]+1))
r[i] = r[j] + 1;
for(i=1; i<=n; i++)
if(!m || m>l[i]+r[i]-1)
m = l[i] + r[i] -1, mi=i;
out<<m<<'\n';
for(i=mi; i<=n; i++)
if(l[i]+r[i]-1 == m && x[mi] <= x[i])
out<<i<<' ', mi=i;
return 0;
}