Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Бодолт илгээх Бүх бодолтууд Шилдэг бодолтууд PDF Жагсаалт руу буцах

RGB7640 - Төлбөр

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

Input

Эхний мөрөнд хүснэгтийн хэмжээ N ба M тоонууд өгөгдөнө. (1<=N,M<=20 )

Дараагийн N мөр бүрт M тоонууд. Тухайн харгалзах нүдэн дэх төлбөрийн хэмжээ 0-оос 100 хүртэлх бүхэл тоо. 

Output

Баруун доод нүд хүрэх замд төлөх хамгийн бага дүн.

Example

Input:

 3 4

1 1 1 1

5 2 2 100

9 4 2 1

Output:

8

 

 

Submit solution!
Нэмсэн:Bataa
Огноо:2013-04-03
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
hide comments
2023-12-21 02:16:34
#include<bits/stdc++.h>

using namespace std;

int main() {
int a[25][25], dp[25][25] = {0};
int n, m;
cin >> n >>m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
dp[1][1] = a[1][1];
for (int i = 2; i <= n; i++) {
dp[i][1] = dp[i - 1][1] + a[i][1];
}
for (int j = 2; j <= m; j++) {
dp[1][j] = dp[1][j - 1] + a[1][j];
}
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= m; j++) {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
cout << dp[n][m];
return 0;
}deelii bla

Last edit: 2023-12-21 02:17:22
2020-05-06 13:10:08
#include <bits/stdc++.h>
using namespace std;
int a[25][25],dp[25][25] = { 0 };
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
dp[1][1]=a[1][1];
for(int i=2;i<=n;i++){
dp[i][1]=dp[i-1][1]+a[i][1];
}
for(int j=2;j<=m;j++){
dp[1][j]=dp[1][j-1]+a[1][j];
}
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
cout<<dp[n][m];
}
2020-05-06 12:09:24
no comment lol
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.