Yêu em Thu Nga CN12 ptit
Senior Member
Này qhđ căn bản làm được mà, y hệt bài trên web trường e, mà thêm cho đi chéo nữa.
Cho bảng A[] kích thước N x M (N hàng, M cột). Bạn được phép đi xuống dưới, đi sang phải và đi xuống ô chéo dưới. Khi đi qua ô (i, j), điểm nhận được bằng A[j].
Hãy tìm đường đi từ ô (1, 1) tới ô (N, M) sao cho tổng điểm là nhỏ nhất.
C++:
#include<bits/stdc++.h>
#define faster() ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef double ld;
typedef long long ll;
typedef unsigned long long ull;
void solve(int a[500][500],int n, int m){
vector<vector<int> >dp(n+1,vector<int>(m+1,INT_MAX));
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+a[i-1][j-1];
}
}
cout<<dp[n][m];
}
int main(){
faster();
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
int a[500][500];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) cin>>a[i][j];
}
solve(a,n,m);
cout<<'\n';
}
return 0;
}
)
