Teamwork

Teanwork
题面

题意
有n头奶牛，我们可以让连续的奶牛组成一队，组队后队里所有奶牛的等级就会变成队里等级最高的那个，求n头奶牛经过组队后，所有奶牛的等级之和最大的是多少。一队奶牛的数量最多不超过C头牛。
分析
这题很容易看出是属于dp类型问题，那是因为该问题可以由它的子问题求解出来。我们设dp[i]表示前i头牛可以达到的最大等级，那么dp[i]可以由dp[i-1]、dp[i-2]、dp[i-3]、…dp[i-k+1]转移过来的，例如dp[i]是由dp[j]转移过来的，我们就可以利用max(dp[i],dp[i-j]+maxn*j) 其中maxn表示i-j+1 、i-j+2…i的最大值。那么就可以使用dp一步一步处理

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
ll s[10005];
ll dp[10005];
int main(){
ll n,k,ma;
cin>>n>>k;
for(ll i=1;i<=n;i++)
	cin>>s[i];
for(ll i=1;i<=n;i++){
	ma=s[i];
	for(ll j=1;j<=k&&i>=j;j++){
		dp[i]=max(dp[i],dp[i-j]+ma*j);
	         ma=max(ma,s[i-j]);
	}
}
cout<<dp[n]<<endl;
}