博客

Description

Input

Output

Please print the highest possible sum of skill levels FJ can achieve by grouping appropriate consecutive sets of cows into teams.

Sample Input

7 3

1

15

7

9

2

5

10

Sample Output

84

Hint

题意：

给你一个数组，让你将这个数组分为一些区间，区间最多包含不超过k个数，然后可以将这个区间全部变成这个区间的最大值，问你划分区间之后所有值的和最大是多少。

题解：

由于n是1e4，k是1e3，那么我们可以O(n

k)的时间复杂度。

状态转移方程：dp[i+j-1]=max(dp[i+j-1],dp[i-1]+j

mx);

#include<bits/stdc++.h>
using namespace std;
int dp[100005];
int a[100005];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        int mx=a[i];
        for(int j=1;j<=k;j++)
        {
            if(a[i+j-1]>mx)
                mx=a[i+j-1];
            dp[i+j-1]=max(dp[i+j-1],dp[i-1]+j*mx);
        }
    }
    printf("%d\n",dp[n]);
    return 0;
}