http://mendo.mk/jforum/posts/list/8.page JForum - http://www.jforum.net [code]#include <bits/stdc++.h>

using namespace std;

int main()
{
int n, m, a[50][50], dp[50][50] = {};
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
dp[0][0] = a[0][0];
for (int i = 1; i < n; i++)
dp[0][i] = a[0][i] + dp[0][i-1];
for (int i = 1; i < m; i++)
dp[i][0] = a[i][0] + dp[i-1][0];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1]);
cout << dp[n-1][m-1] << endl;
int i = m - 1, j = n - 1;
cout << "1 1" << endl;
while (i || j)
{
if (dp[i][j] - a[i][j] == dp[i-1][j])
i--;
else
j--;
cout << m - j << " " << n - i << endl;
}
return 0;
}
[/code]
Проблемот е што имам точен резултат но погрешен пат, бидејќи ги има повеќе патишта. Како да знам кој е оптималниот пат во задачата? Тест пример:
Влез:
5 5
2 3 4 5 1
1 1 2 4 3
1 3 1 3 1
4 6 3 4 2
3 3 1 1 2
Точен излез:29
1 1
1 2
1 3
1 4
2 4
3 4
4 4
4 5
5 5
Кориснички излез:29
1 1
1 2
2 2
2 3
2 4
2 5
3 5
4 5
5 5]]> http://mendo.mk/jforum/posts/preList/662/3632.page http://mendo.mk/jforum/posts/preList/662/3632.page GMT
Тргни од крајот.
[code]#include <bits/stdc++.h>

using namespace std;

int main()
{
int n, m, a[50][50], dp[50][50] = {};
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
dp[0][0] = a[0][0];
for (int i = 1; i < n; i++)
dp[0][i] = a[0][i] + dp[0][i-1];
for (int i = 1; i < m; i++)
dp[i][0] = a[i][0] + dp[i-1][0];
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1]);
cout << dp[n-1][m-1] << endl;

vector<pair<int, int> > result;

int i = m - 1, j = n - 1;
result.push_back({i+1, j+1});

while (i != 0 || j != 0) {

if (i > 0 && dp[i][j] == dp[i-1][j] + a[i][j]) {
i--;
} else {
j--;
}

result.push_back({i+1, j+1});
}

reverse(result.begin(), result.end());
for (auto r : result) {
cout << r.first << " " << r.second << endl;
}


return 0;
}[/code]]]> http://mendo.mk/jforum/posts/preList/662/3634.page http://mendo.mk/jforum/posts/preList/662/3634.page GMT
Тргни од крајот.
[/quote]
Фала сега работи, меѓутоа нели го правам истото во горниот код? Сакав да скратам неколку редови код.]]> http://mendo.mk/jforum/posts/preList/662/3637.page http://mendo.mk/jforum/posts/preList/662/3637.page GMT Сакав да скратам неколку редови код.[/quote]
Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).]]> http://mendo.mk/jforum/posts/preList/662/3638.page http://mendo.mk/jforum/posts/preList/662/3638.page GMT Сакав да скратам неколку редови код.[/quote]
Не баш, разгледуваш една позиција (i, j) а печатиш одлуки за друга (m - j, n-i).[/quote]
Да, ама ова се случува кога двата елементи имаат исти збир, зошто не и кај вториот алгоритам, бидејќи и таму постојат 2 патишта а во решението е можно да е одбран друг од 2та точни патишта, или постои само 1 точен?]]> http://mendo.mk/jforum/posts/preList/662/3639.page http://mendo.mk/jforum/posts/preList/662/3639.page GMT