NC24190. [USACO 2018 Dec G]Teamwork
描述
Farmer John的N头奶牛（1≤N≤10^4）排成一行，方便起见依次编号为1…N。奶牛i的包装礼物的技能水平为si。她们的技能水平可能参差不齐，所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过K头的连续的奶牛（1≤K≤10^3），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。
请帮助FJ求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。
输入描述
输入的第一行包含N和K。以下N行按照N头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过10^5的正整数。
输出描述
输出FJ通过将连续的奶牛进行分组可以达到的最大技能水平和。
示例1
输入:
7 3 1 15 7 9 2 5 10
输出:
84
说明:
在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于K）。这样能够有效地将7头奶牛的技能水平提高至15、15、15、9、10、10、10，和为84。C++14(g++5.4) 解法, 执行用时: 35ms, 内存消耗: 604K, 提交时间: 2019-06-10 16:30:15
#include<bits/stdc++.h>
using namespace std;
int n,x[10086],m,k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&x[i]);
int dp[10086]={0};
for(int i=1;i<=n;i++){
int max1=x[i];
for(int j=i;j>=1&&j>i-k;j--){
max1=max(max1,x[j]);
dp[i]=max(dp[i],dp[j-1]+max1*(i-j+1));
}
}
printf("%d",dp[n]);
}
C++11(clang++ 3.9) 解法, 执行用时: 51ms, 内存消耗: 588K, 提交时间: 2020-03-17 17:50:21
#include<bits/stdc++.h>
using namespace std;
int a[1000010],dp[1000010];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int maxn=a[i];
for(int j=i;j>=1&&i-j<k;j--)
{
maxn=max(maxn,a[j]);
dp[i]=max(dp[i],dp[j-1]+maxn*(i-j+1));
}
}
cout<<dp[n]<<endl;
return 0;
}