USACO 2018 - Dec - Gold - Teamwork
View as PDF
Vào kì nghỉ yêu thích của mình, người nông dân John muốn gửi tới những người bạn của mình một số món quà. Bởi vì không giỏi gói quà, John đã nhờ những chú bò của mình giúp sức.
~N~ chú bò của nông dân John xếp thành một hàng, đánh số từ ~1...N~. Chú bò thứ ~i~ có kĩ năng gói quà là ~a_{i}~. Vì những chỉ số này không đồng đều nên John muốn chia các chú bò thành từng đội. Mỗi đội gồm tối đa ~K~ chú bò liên tiếp nhau. Mỗi chú bò phải trong chính xác một đội. Bởi vì các chú bò có thể học hỏi lẫn nhau nên kĩ năng gói quà của mỗi chú bò được tăng lên bằng kĩ năng gói quà lớn nhất trong đội.
Hãy giúp nông dân John tìm cách chia đội tối ưu nhất và tìm xem tổng kĩ năng gói quà của các chú bò trong phương án tối ưu nhé!
Input
Dòng đầu chứa hai số nguyên dương ~N~ và ~K~ ~(1 \le N \le 10^4, 1 \le K \le 10^3)~.
~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~a_{i} (1 \le a_{i} \le 10^5)~ - kĩ năng gói quà của chú bò thứ ~i~.
Output
- Ghi ra tổng kĩ năng gói quà trong phương án tối ưu.
Sample Input
7 3
1
15
7
9
2
5
10
Sample Output
84
Giải thích
- Nhóm 3 chú bò đầu, 3 chú bò sau và chú bò giữa 1 nhóm riêng. Tổng kĩ năng là ~15 + 15 + 15 + 9 + 10 + 10 + 10 = 84~
Comments
include <bits/stdc++.h>
using namespace std; const int N=1e4+5; int n,k,a[N],f[N]; int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++){ int m=0; for(int j=0;j<k&&i-j>0;j++){ m=max(m,a[i-j]); f[i]=max(f[i],f[i-j-1]+m*(j+1)); } } cout<<f[n]; }