FLOWER - Khăn đỏ và bó hoa tặng bà
Xem dạng PDF
Trên đường từ nhà bé Khăn đỏ (trong truyện cô bé quàng khăn đ) đến nhà bà ngoại phải đi qua một khu rừng. Khu rừng hình chữ nhật được chia thành ~M~ hàng ~N~ cột, hàng được đánh số từ ~1~ đến ~M~, cột được đánh số từ ~1~ đến ~N~, ô ở hàng ~i~, cột ~j~ được ký hiệu là ô ~(i, j)~. Nhà bé khăn đỏ ở ô ~(1, 1)~ còn nhà bà ngoại ở ô ~(M, N)~, chẳng hạn với ~M = 4, N = 5~ ta có hình vẽ như sau (Nhà bé khăn đỏ ở ô màu đỏ, nhà bà ngoại ở ô màu xanh):
Trên khu rừng, có một số ô có bông hoa, một số ô không có gì và một số ô có sói hung dữ mà ta không thể đi vào đó.
Ta quy ước những ô có số ~-1~ là có sói, những ô có số ~0~ là không có gì và những ô có số nguyên dương là có bông hoa với độ đẹp là số nguyên dương đó.
Hôm nay, bà ngoại bị ốm và mẹ sai bé khăn đỏ mang cơm cho bà. Khi đi mẹ có dặn bé khăn đỏ không được la cà, tức là từ một ô chỉ có thể đi sang ô kề cạnh phía bên phải hoặc kề cạnh phía dưới (tất nhiên là ô đó phải không có sói).
Trên đường đi, bé khăn đỏ muốn hái tặng bà một bó hoa đẹp nhất. Em hãy tính xem bó hoa đẹp nhất mà bé khăn đỏ có thể hái được là bao nhiêu và hãy giúp bé khăn đỏ hiếu thảo tìm một đường đi để hái được bó hoa như vậy nhé (Ở đây ta quy ước “độ đẹp” của bó hoa là tổng “độ đẹp” của tất cả các bông hoa của bó hoa đó).
Input
- Dòng đầu chứa hai số nguyên dương ~M, N~ cách nhau bởi một khoảng trắng;
- ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ~N~ số nguyên ~a_{ij}~ là thông tin về các ô trên hàng thứ ~i~.
Giới hạn:
- ~2 ≤ N, M ≤ 1000, -1 ≤ a_{ij} ≤ 1000~
Output
- Ghi ra một dòng duy nhất là “độ đẹp” của bó hoa đẹp nhất hái được (nếu không thể đến được nhà bà thì ghi ra số ~-1~) ;
Sample
Input #1
4 5
0 3 0 0 0
1 -1 2 5 0
1 2 -1 -1 0
-1 1 1 1 0
Output #1
10
Hint
- Những ô tô màu vàng là hành trình đi (trừ ô đầu và ô cuối)
Problem source: Chuyên Sơn La Online Judge
Bình luận
CODE CUA MINH CHO CAC BN THAM KHAO
include<bits/stdc++.h>
define t1dt iosbase::syncwith_stdio(false);cin.tie(nullptr);
using namespace std; using ll = long long int; const ll INF=1e18; int main() { t1dt //if (fopen("INPUT.INP", "r")) { // freopen("INPUT.INP", "r", stdin); // freopen("OUTPUT.OUT", "w", stdout); //} ll n,m; cin>>n>>m; vector a(n+1,vector<ll>(m+1));
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
cin>>a[i][j];
}
}
vector dp(n+1,vector<ll>(m+1,-INF));
if(a[1][1]==-1){
cout<<-1;
return 0;
}
dp[1][1]=max(0LL,a[1][1]);
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
if(i==1&&j==1) continue;
if(a[i][j]==-1)continue;
ll best=-INF;
if(i>1&&j>1){
best=max(dp[i-1][j],dp[i][j-1]);
} else if(i>1){
best=dp[i-1][j];
} else if(j>1){
best=dp[i][j-1];
}
if(best!=-INF){
if(a[i][j]>0) dp[i][j]=best+a[i][j];
else dp[i][j]=best;
}
}
}
if(dp[n][m]==-INF) cout<<-1;
else cout<<dp[n][m];
return 0;
}
include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4;
int main() { ios::syncwithstdio(false); cin.tie(nullptr);
}
include <bits/stdc++.h>
using namespace std; const long long NEG = LLONGMIN / 4; int main() { ios::syncwith_stdio(false); cin.tie(nullptr);
}
Code chatgpt à?? sao nhìn giống AI code thế??
Thì có sao đâu bạn ? những người không biết đáp án nhìn vô đây đọc đc là đc mà .