Question

Problema plopi1 (#397) de pe pbinfo... imi poate spune cineva unde gresesc sau imi poate explica o rezolvare?

#include
#include

using namespace std;

ifstream fin("plopi1.in");
ofstream fout("plopi1.out");

int n, i, v[1050], aux[1050], j, maxi, k, maxi1, pos, maxx;

void afisare()
{
for (i=1;i<=n;i++)
cout << v[i] << " ";
cout << endl;
for (i=1;i<=n;i++)
cout << aux[i] << " ";
cout << endl;
}

int main ()
{
fin >> n;
for (i=1;i<=n;i++)
fin >> v[i];
aux[n] = 0;
for (i=n-1;i>=1;i--)
for (j=i;j<=n;j++)
if (v[j] < v[i])
aux[i]++;
for(i=1;i<=n;i++)
{
if (aux[i] > maxi)
{
maxi = aux[i];
pos = i;
k = 1;
}
maxx = v[pos];
}
afisare();
while(maxi > 0)
{
maxi1 = 0;
for (i=pos+1;i<=n;i++)
{
if (aux[i] > maxi1 && aux[i] < maxi && maxx > v[i])
{
maxi1 = aux[i];
pos = i;
}
}
maxi = maxi1;
maxx = v[pos];
k++;
}
cout << k;
fin.close();
fout.close();
return 0;
}

Answer 1

Problema Plopi1 este o problema de dinamica si este de tipul problemei rucsacului. Studiaza aceasta problema, cazul continuu (dinamica) si impreuna cu solutia oficiala cred ca ai s-o intelegi. Succes!
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 1005

ifstream fin("plopi1.in");
ofstream fout("plopi1.out");

int n, a[NN], L[NN];


int main(){
assert(fin >> n );
for(int i=1 ; i<=n ; ++i)
assert(fin >> a[i]);
L[n] = 1;
for(int i=n-1 ; i>0 ; i--)
{
L[i] = 1;
for(int j=i+1 ; j<=n; ++j)
if(a[i]>a[j] && L[i]<L[j]+1)
L[i] = L[j] + 1;
}
int pmax = 1;
for(int i=1 ; i<=n ; ++i)
if(L[pmax] <= L[i])
pmax = i;
fout << n - L[pmax] << endl;
return 0;
}