Ĺadny brzuch
Mamy ciąg liczb. Jak obliczyc (pewnie dynamicznie ale dokladniej?) największą mozliwą sumę jego wyrazów, takich, ze podciag nie zawiera zadnych dwoch kolejnych wyrazów z ciągu wyjsciowego?
Masz jakąś sprawdzarkę do tego? Naskrobałem takie coś, ale nie jestem pewien czy to działa (chyba byłoby za prosto - pewnie źle zrozumiałem zadanie):
#include <cstdio> #define max(a,b) ((a>b)?(a):(b)) int main() { Â int n; Â scanf("%d",&n); Â int maxWithPrev = 0; Â int maxWithoutPrev = 0; Â for(int i=0;i<n;i++) Â { Â int a; Â scanf("%d",&a); Â if(a<0) a = 0; Â int tmp = maxWithoutPrev; Â maxWithoutPrev = maxWithPrev; Â maxWithPrev = max(tmp+a,maxWithPrev); Â } Â printf("%d",max(maxWithPrev,maxWithoutPrev)); Â return 0; }
Użytkownik bryn edytował ten post 03 luty 2009, 11:02
Oficialnej sprawdzaczki nie mam, ale na moich testach (tych najbardziej zlosliwych xD) daje dobre wyniki wiec pewnie ogolnie jest ok ;] thx
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
Masz jakąś sprawdzarkę do tego? Naskrobałem takie coś, ale nie jestem pewien czy to działa (chyba byłoby za prosto - pewnie źle zrozumiałem zadanie):
#include <cstdio> #define max(a,b) ((a>b)?(a):(b)) int main() { Â int n; Â scanf("%d",&n); Â int maxWithPrev = 0; Â int maxWithoutPrev = 0; Â for(int i=0;i<n;i++) Â { Â int a; Â scanf("%d",&a); Â if(a<0) a = 0; Â int tmp = maxWithoutPrev; Â maxWithoutPrev = maxWithPrev; Â maxWithPrev = max(tmp+a,maxWithPrev); Â } Â printf("%d",max(maxWithPrev,maxWithoutPrev)); Â return 0; }
Użytkownik bryn edytował ten post 03 luty 2009, 11:02
Oficialnej sprawdzaczki nie mam, ale na moich testach (tych najbardziej zlosliwych xD) daje dobre wyniki wiec pewnie ogolnie jest ok ;] thx