Am luat problema ZigZag de pe topcoder,
http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 , am facut (bine, zic eu) algoritmul dar nu merge bine afisarea.
#include <fstream>
#define k 300
using namespace std;
int l[k], a[k], p[k], n, lmax, val=-1;
// p[i] = valoarea precedenta de a[i]
ifstream f("sec.in");
ofstream g("sec.out");
int sc(int a, int b)
{
if(b-a>0) return 0;
return 1;
}
// sc returneaza 0 sau 1, in functie de diferenta (pozitiva sau negativa)
int afis(int poz)
{
if(poz==1) return 0;
if(!lmax)
{ if(val!=-1)
while(l[poz] != lmax || ( sc(p[poz], a[poz]) == sc(a[poz], a[val]) )) poz--;
g << a[poz] << " ";
lmax--;
val = poz;
afis(poz-1);
}
}
//afisul, care afiseaza dupa pozitie
int main()
{
int i, j, x, y, poz;
f >> n;
for(i=1; i<=n; i++) f >> a[i];
l[1] = 1;
l[2] = 2;
p[1] = 0;
p[2] = a[1];
for(i=3; i<=n; i++)
{ l[i] = 1;
for(j=1; j<i; j++)
{
x = sc(a[j], a[i]);
y = sc(p[j], a[j]);
if(l[j]+1>l[i] && x!=y)
{ l[i] = l[j]+1;
p[i] = a[j];
if(lmax<l[i]) lmax=l[i], poz=i;
}
}
}
//afisarea
afis(poz);
f.close();
g.close();
return 0;
}
ma poate ajuta cineva cu o idee ceva la afis? nu inteleg de ce nu merge... algoritmul zic ca ii bun