Titlul: Problema secventa
Scris de: Jurj Andrei din Februarie 18, 2014, 17:54:29
M-am chinuit la o problema cu secvente dar nu i-am dat de cap unde e greseala(nu de compilare ci a algoritmului).Sincer cred ca vreun indice e problema da nu-mi dau seama care. Problema este:determinati secventa palindromica de lungime maxima.(la lungimi egale se ia cea mai din stanga).Stiu ca aceasta complexitate e mare dar in enunt n<=1000 deci timpul nu este o problema. #include<fstream> using namespace std; ifstream f("secvpal.in"); ofstream g("secvpal.out"); int v[1005]; int main() {int n,i,stmax,drmax,j,k,l,difmax=0,dif,var,var2=1,var3=1; f >>n; for(i=1;i<=n;++i) f >>v[i]; for(i=1;i<=n&&(n-i)>difmax;++i) {j=n;var3=1;var2=1; while(j>i&&var3) {var2=1; while(v[i]!=v[j]&&var2) {--j; if(j<=i)var2=0; } if(v[i]==v[j]&&var2) { dif=j-i+1;var=1; if(dif%2==0) for(k=i,l=1;l<=dif/2&&var;++k,++l) if(v[k]!=v[j-l+1]) var=0; else { for(k=i,l=1;l<dif/2&&var;++k,++l) if(v[k]!=v[j-l+1]) var=0; if(v[k]!=v[j-l+1]) var=0; }
if(var==1) if(dif>difmax) {stmax=i,drmax=j,difmax=dif,var3=0;}
} --j; } }
g<<stmax<<" "<<drmax;
}
Am reusit singur pana la urma(stiu ca e complexitate mare dar macar a mers.Era ceva problema la acolade..Cine doreste solutia este: #include<iostream> #include<fstream> using namespace std; ifstream f("secvpal.in"); ofstream g("secvpal.out"); int v[1005]; int main() {int n,i,j,k,l,difmax=0,st,dr,var,dif,var2; f >>n; for(i=1;i<=n;++i) f >>v[i]; for(i=1;i<n;++i) {j=n;var2=1; while(j>i&&var2) { while(v[i]!=v[j]&&j>i) --j; if(j>i) if(v[i]==v[j]) {dif=j-i+1;var=1; if(dif%2==0) for(k=i,l=1;l<=dif/2&&var;++l,++k) {if(v[k]!=v[j-l+1]) var=0;
} else for(k=i,l=1;l<dif/2&&var;++k,++l) {if(v[k]!=v[j-l+1]) var=0;
} if(var) if(dif>difmax) st=i,dr=j,difmax=dif,var2=0;
} --j;
}
} g<<st<<" "<<dr; f.close(); g.close(); return 0; }
|