Mendo Judge Discussion Board - Forums
Search
Recent Topics
Hottest Topics
Member Listing
Back to home page
Задача Зајак МОИ 2015
Forum Index
»
Задачи од национални натпревари
Author
Message
17/01/2019 15:15:07
Subject:
Задача Зајак МОИ 2015
MODDI
Joined: 27/12/2017 18:17:00
Messages: 39
Offline
Ја решавав задачата Зајак од МОИ 2015, ми работи на 3/25 , помош околу кодов.
#include <iostream> using namespace std; int main() { int N,M; cin>>N>>M; int MAT[N][M]; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { cin>>MAT[i][j]; } } int dp[N][M]; dp[0][0]=MAT[0][0]; for(int i=1;i<N;i++) dp[i][0]=dp[0][0]+MAT[i][0]; for(int i=1;i<M;i++) dp[0][i]=dp[0][0]+MAT[0][i]; for(int i=1;i<N;i++) { for(int j=1;j<M;j++) { dp[i][j]=dp[i-1][j]+MAT[i][j]; } } cout<<dp[N-1][M-1]<<endl; return 0; }
18/01/2019 19:15:51
Subject:
Задача Зајак МОИ 2015
longhi
Joined: 16/01/2019 22:52:02
Messages: 18
Offline
MODDI wrote:
Ја решавав задачата Зајак од МОИ 2015, ми работи на 3/25 , помош околу кодов.
Не е баш така, кодов како да е за некоја друга задача.
Јас вака би поправил, имаш коментари во програмата ако нешто не е јасно.
#include <iostream> #include <cstring> using namespace std; int main() { int N,M; cin>>N>>M; int MAT[N][M]; for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { cin>>MAT[i][j]; } } int dp[N][M]; memset(dp, 0, sizeof(dp)); dp[0][0] = MAT[0][0]; for (int j=1; j < M; j++) { //vo vtoriot red mozheme da dojdeme taka shto kje //pochneme od [0][0] pa skokame do nekoe pole vo istiot //red, pa potoa edna kolona nadolu dp[1][j] = MAT[0][0] + MAT[0][j] + MAT[1][j]; } //za sekoj nareden red for (int i=1; i+1 < N; i++) { //najdi gi dvata najgolemi elementi vo ovaa redica int max1 = 0, max2 = 0; for (int j=0; j<M; j++) { if (dp[i][j] >= max1) { max2 = max1; max1 = dp[i][j]; } else if (dp[i][j] > max2) { max2 = dp[i][j]; } } for (int j=0; j<M; j++) { //najdobro e da skokneme od najgolemiot element vo redicata //do ova pole, pa potoa eden chekor nadolu int max_value = max1; if (dp[i][j] == max1) { //ne mozheme da skokneme na istoto pole, zemi go vtoriot maximum max_value = max2; } dp[i+1][j] = max(dp[i+1][j], max_value + MAT[i][j] + MAT[i+1][j]); } } //vo posledniot red mozheme da skokneme do poslednata kolona for (int j=0; j+1 < M; j++) { dp[N-1][M-1] = max(dp[N-1][M-1], dp[N-1][j] + MAT[N-1][M-1]); } cout<<dp[N-1][M-1]<<endl; return 0; }
Forum Index
»
Задачи од национални натпревари
Go to:
Select a forum
Добродојдовте!
Општа дискусија
Задачи од национални натпревари
Задачи од меѓународни натпревари
Други задачи
Регионални натпревари
Државни натпревари
Македонски Олимпијади
Други натпревари
Pascal
C/C++
Јава
Други јазици
Powered by
JForum 2.1.8
©
JForum Team