Friday, December 5, 2008

Хоёр хэмжээст массивийн хэрэглээ

SPOJ-ын бодлогын архив2797.
Жимс
Бодлогын дугаар: CODE0004

Бяцхан сармагчин жимс цуглуулахаар явж байв. Тэрээр байгаа чулууны баруун урд, эсвэл зүүн урд чиглэлийн чулуу уруу л шилжиж чадна. Чулуу болгонд тодорхой хэмжээний жимс байх бөгөөд эцсийн шатанд сармагчиний авч чадах хамгийн их жимсний тоог ол.


InputN:

Эхний мөр нийт шилжилтийн тоо. a(i,j), 1 < = j < = i < = N Чулуу болгон дээр байгаа жимсний тоо 0 < = N, a(i,j) <= 200,


Output


Цуглуулж чадах хамгийн их жимсний тоо



Example


Input:


3

0

3 1

1 2 2


Output:

5


Шийдэл: Эхлээд N-1 дэх мөрийг авч үзье. Тэгвэл a[n-1,i] дээр max(a[n,i],a[n,i+1]) ийг нэмье.Дараа нь N-2 дэх мөрийг авч мөн уг үйлдлийг хийнэ. Энэ алхмыг үргэлжлүүлсээр 1 дэх мөр хүртэл хийнэ. Ингээд a[1,1] нь анхны бодлогын хариу болно.



#include "stdio.h"
main()
{
int n,i,j;
int a[90][90]={0};
scanf("%d",&n);
for(i=0; i<n; i++)
{
for(j=0; j<=i; j++)
scanf("%d",&a[i][j]);
}

for(i=n-2; i>=0; i--)
{
for(j=0; j<=n-2; j++)
if(a[i+1][j]>a[i+1][j+1]) a[i][j]+=a[i+1][j];
else a[i][j]+=a[i+1][j+1];
}
printf("%d",a[0][0]);
return 0;
}

Бодлогын эх сурвалж:
Програмчлал, Алгоритм сонирхогчдод зориулав
Чимэдээ ахын бодлогын сайт
Шийдлийг: Кодер.МН блог

3 comments:

Tengis said...

За энэ ч гэсэн алдаатай юм бишүү засаарай засахаар нь үзнээ ok

Хонгор said...

Шийдэл дээрээ блог дурдсанд баярлалаа.

Гансүх said...

Алдааг засав. ОК

:)) ;)) ;;) :D ;) :p :(( :) :( :X =(( :-o :-/ :-* :| 8-} :)] ~x( :-t b-( :-L x( =))

Post a Comment