Pagini recente » Diferente pentru teorema-chineza-a-resturilor intre reviziile 68 si 67 | Cod sursa (job #1237302)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define NN 100009
using namespace std;
ofstream out("scmax.out");
int dp[NN] , v[NN] , poz[NN];
int p , mmax , n ;
void Read();
void Scm();
void Write();
int main()
{
Read();
Scm();
Write();
return 0;
}
void Read()
{
ifstream in("scmax.in");
in >> n;
for( int i = 1; i<=n ; i++)
in >> v[i];
}
void Scm()
{
/*
dp[1] = 1;
poz[1] = -1;
mmax = -1;
p = n;
for( int i = 2 ; i <=n ; i++ )
{
dp[i] = 1;
poz[i] = -1;
for( int j = 1 ; j < i ; ++j )
if( v[i] > v[j] )
if( dp[i] < dp[j] + 1 )
{
dp[i] = dp[j] + 1;
poz[i] = j;
if( dp[i] > mmax )
mmax = dp[i] , p = i;
}
}
*/
dp[n] = 1;
poz[n] = -1;
mmax = -1;
p = n;
for( int i = n - 1; i >=1 ; --i )
{
dp[i] = 1;
poz[i] = -1;
for( int j = i + 1 ; j<=n ; ++j )
if( v[i] < v[j] )
if( dp[i] < dp[j] + 1 )
{
dp[i] = dp[j] + 1;
poz[i] = j;
if( dp[i] > mmax )
mmax = dp[i] , p = i;
}
}
}
void Write()
{
out << mmax << '\n';
int i = p;
// vector < int > sol;
while( i != -1 )
{
// sol.push_back(v[i]);
out << v[i] << " ";
i = poz[i];
}
/*
reverse( sol.begin() , sol.end() );
for( int i = 0 ; i < sol.size() ; ++i )
out << sol[i] << " ";
*/
}