Cod sursa(job #2155525)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 7 martie 2018 21:52:15
Problema Subsir 2 Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
int v[5005],dp[5005],last[5005],sol[5005];
int main(){
freopen("subsir2.in","r",stdin);
freopen("subsir2.out","w",stdout);
int n,i,rasp=2000000000,j,num;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
num=n+1;
v[n+1]=2000000000;
for(i=1;i<=n;i++){
dp[i]=2000000000;
int maxim=-2000000000;
last[i]=n+1;
for(j=i-1;j>=1;j--){
if (maxim<v[j] && v[j]<=v[i]){
dp[i]=min(dp[i],dp[j]+1);
if (dp[i]==dp[j]+1 && v[j]<v[last[i]])
last[i]=j;}
if (v[j]>maxim && v[j]<=v[i])
maxim=v[j];}
if (dp[i]==2000000000)
dp[i]=1;}
int maxim=-2000000000;
for(i=n;i>=1;i--){
if (maxim<v[i]){
rasp=min(rasp,dp[i]);
if (rasp==dp[i])
if (v[i]<v[num])
num=i;}
maxim=max(maxim,v[i]);}
printf("%d\n",rasp);
int u=0;
while(dp[num]!=1){
sol[++u]=num;
num=last[num];}
sol[++u]=num;
assert(u==rasp);
for(i=u;i>=1;i--)
printf("%d ",sol[i]);
return 0;}