Cod sursa(job #2155564)

Utilizator ovidius11Stiriu Ovidius ovidius11 Data 7 martie 2018 22:23:32
Problema Subsir 2 Scor 96
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
int v[5005],dp[5005],last[5005],sol[5005],aux[5005],aux2[5005];
int cmp(int x,int y){
int u=0;
while(dp[x]!=1){
aux[++u]=x;
x=last[x];}
aux[++u]=x;
int u2=0;
while(dp[y]!=1){
aux2[++u2]=y;
y=last[y];}
aux2[++u2]=y;
assert(u==u2);
int i;
for(i=u;i>=1;i--)
if (v[aux[i]]<v[aux2[i]])
return 1;
else
if (v[aux[i]]>v[aux2[i]])
return 0;
return 0;}
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]){
if (dp[i]>dp[j]+1)
dp[i]=dp[j]+1,last[i]=j;
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]){
if (rasp>dp[i])
rasp=dp[i],num=i;
if (rasp==dp[i])
if (cmp(i,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;
for(i=u;i>=1;i--)
printf("%d ",sol[i]);
return 0;}