Jak zrobić zadanie gra ? (c++, programowanie dynamiczne)

pytanie zadane 18 sierpnia 2016 w C i C++ przez hardusername Początkujący (370 p.)

Cześć,

czy moglibyście mi proszę podpowiedzieć jak zrobić takie zadanie?

Limit pamięci: 32 MB

Kolejny deszczowy dzień. Paweł i Gaweł znów byli zmuszeni do pozostania w domu. W związku z brakiem zajęć postanowili wymyślić jakąś grę.

Paweł wpadł na genialny pomysł. Na kartce papieru narysował pól. Na każdym polu znajdowały się dwie liczby - pierwsza z nich była numerem pola (liczba naturalna od do , pola miały parami różne numery), a druga jego wartością (liczba całkowita od do ). Na polu numer umieścił pionek. Zadaniem gracza było wykonywanie kolejnych ruchów, polegających na rzucie sześcienna kostką (z numerami od do napisanymi na ściankach) oraz przesuwaniu pionka o wskazaną liczbę oczek. Gra kończyła się, kiedy pionek stanął na pole o numerze . Wynikiem, jaki uzyskał gracz, była suma wartości pól na jakich stał pionek.

Po rozegraniu kilku partii Paweł i Gaweł otrzymali kilka różnych wyników, jednak nie wiedzieli czy któryś z nich był największym możliwym do uzyskania. Zadzwonili więc do Ciebie, utalentowanego informatyka, abyś napisał program, który dla danej planszy obliczy maksymalny możliwy do uzyskania wynik.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę pól na planszy. Drugi wiersz zawiera liczb całkowitych , , ..., (), gdzie oznacza wartość -tego pola.

Wyjście

Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalny możliwy do uzyskania wynik na danej planszy.

Przykład

Dla danych wejściowych:

4
1 2 -1 1

poprawną odpowiedzią jest:

komentarz 18 sierpnia 2016 przez MetRiko Nałogowiec (37,110 p.)

Czy to nie jest czasem jakieś zadanie na konkurs programistyczny, czy coś w ten deseń?

1	komentarz 18 sierpnia 2016 przez draghan VIP (106,230 p.) http://main.edu.pl/pl/archive/ilocamp/2011/gra Autorze pytania - z czym masz problem? Całego zadania nikt za Ciebie tu nie zrobi. ;)

1 odpowiedź

odpowiedź 18 sierpnia 2016 przez Porcupine Nałogowiec (31,560 p.)

Wyobraź sobie, że stoisz na polu numer n i osiągnąłeś już ten maksymalny wynik. Za razem jakoś musiałeś się na niego dostać - masz koska ma 6 numerków {1,2,3,4,5,6}, wniosek: przyskoczyłeś z jednego z pól o numerku należącym do zbioru {n - 1, n - 2, n - 3, n - 4, n - 5, n - 6}. Teraz pytanie, z którego? - A, no z tego, do którego dojście gwarantuje największą sumę i tak rekurencyjnie zawsze masz 6 możliwości i wybierasz najkorzystniejszą.

Poczytaj o idei programowania dynamicznego i na podstawie powyższej odpowiedzi powinieneś dać radę to zaimplementować.