题目描述

在Farmer John最喜欢的节日里，他想要给他的朋友们赠送一些礼物。由于他并不擅长包装礼物，他想要获得他的奶牛们的帮助。你可能能够想到，奶牛们本身也不是很擅长包装礼物，而Farmer John即将得到这一教训。

Farmer John的头奶牛（）排成一行，方便起见依次编号为。奶牛i的包装礼物的技能水平为。她们的技能水平可能参差不齐，所以FJ决定把她的奶牛们分成小组。每一组可以包含任意不超过头的连续的奶牛（），并且一头奶牛不能属于多于一个小组。由于奶牛们会互相学习，这一组中每一头奶牛的技能水平会变成这一组中水平最高的奶牛的技能水平。

请帮助FJ求出，在他合理地安排分组的情况下，可以达到的技能水平之和的最大值。

输入描述:

输入的第一行包含和。以下行按照头奶牛的排列顺序依次给出她们的技能水平。技能水平是一个不超过的正整数。

输出描述:

输出FJ通过将连续的奶牛进行分组可以达到的最大技能水平和。

示例1

输入
7 3
1
15
7
9
2
5
10
输出
84
说明
在这个例子中，最优的方案是将前三头奶牛和后三头奶牛分别分为一组，中间的奶牛单独成为一组（注意一组的奶牛数量可以小于）。这样能够有效地将7头奶牛的技能水平提高至15、15、15、9、10、10、10，和为84。

解答

表示之间的奶牛被分组完成之后的答案，递推式就是 dp[j] = ∑dp[i] + max(i,j) * (j - i + 1) ( j >= i - k + 1 && j <= i)

静态区间最大值搞个ST表维护下就行了。 

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++) 
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f)) 
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x); 
#define Pri(x) printf("%d\n", x)
#define Prl(x) printf("%lld\n",x); 
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long 
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int N,M,K;
const int SP = 20;
int MAX[maxn][SP];
int mm[maxn];
void initRMQ(int n,LL b[]){
    mm[0] = -1;
    for(int i = 1; i <= n; i ++){
        mm[i] = ((i & (i - 1)) == 0)?mm[i - 1] + 1:mm[i - 1];
        MAX[i][0] = b[i];
    }
    for(int j = 1; j <= mm[n]; j ++){
        for(int i = 1; i + (1 << j) - 1 <= N; i ++){
            MAX[i][j] = max(MAX[i][j - 1],MAX[i + (1 << (j - 1))][j - 1]);
        }
    }
}
int rmq(int x,int y){
    int k = mm[y - x + 1];
    return max(MAX[x][k],MAX[y - (1 << k) + 1][k]);
}
LL a[maxn];
LL dp[maxn];
int main(){
    Sca2(N,K);
    for(int i = 1; i <= N ; i ++) Scl(a[i]);
    initRMQ(N,a);
    for(int i = 1; i <= N ; i ++){
        for(int j = max(1,i - K + 1); j <= i ; j ++){
            dp[i] = max(dp[i],dp[j - 1] + rmq(j,i) * (i - j + 1));
        }
    }
    Prl(dp[N]);
    return 0;
}

来源：Hugh_Locke