Đề bài: $\href{https://codeforces.com/problemset/problem/416/B}{Đây}$
Tóm tắt: Cho n người vẽ và m bức tranh, cùng với ma trận m*n. Trong đó t_ij cho biết thời gian người thứ i hoàn thành bức tranh thứ j. Một bức tranh được vẽ lần lượt từ người thứ nhất đến người thứ hai... cho đến người thứ n, và tất cả những người này làm việc liên tục và không có thời gian nghỉ ngơi. Thời điểm bắt đầu là 0. Hãy in tất cả thời điểm người thứ n hoàn thành tất cả các bức tranh.
Lời giải: Goi $dp[i][j]$ là thời điểm mà người thứ i kết thúc bức tranh thứ j.
Khi đó ta có công thức dp như sau: $dp[i][j]=max(dp[i][j-1],dp[i-1][j])+t[i][j]$.
Từ đây ta chỉ việc thực hiện tính toán mảng dp là xong, các bạn có thể xem thêm tại source
Souce:
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define inf -1000000000000000000
- int main(){
- ll m,n;
- cin>>m>>n;
- ll a[m][n];
- ll i,j;
- for(i=0;i<m;i++)
- for(j=0;j<n;j++) cin>>a[i][j];
- ll dp[n][m];
- dp[0][0]=a[0][0];
- for(i=1;i<n;i++) dp[i][0]=dp[i-1][0]+a[0][i];
- for(j=1;j<m;j++){
- for(i=0;i<n;i++) dp[i][j]=max((j>0?dp[i][j-1]:inf),(i>0?dp[i-1][j]:inf)) + a[j][i];
- }
- for(j=0;j<m;j++) cout<<dp[n-1][j]<<" ";
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét