【题解】聪明伶俐的香穗子

佚名 6年前 (2019-05-10) 随笔 919人围观抢沙发百度已收录

题目描述

　　聪明的香穗子遇到难题了：一个序列上有n个整数，现在你要取m个，且这m个数的任意两个不能相隔太近，问能得到的数字和最大值是多少。

输入格式

　　第一行三个数n，m，k，分别表示n个数，取m个，且m个中的任意两个位置差要大于等于k；

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　第二行有n个整数，表示序列上的每个数。

输出格式

　　一行，输出符合条件的最大和。

输入样例

4 2 2

3 4 -5 1

输出样例

题解

　　容易想到我们设$f[i][j]$为选择$a[i]$且刚好选择了$j$个物品的最大值，那么容易得到$f[i][j] = a[i] + \underset{1 \leqslant l \leqslant i - k}{max} \left \{ f[l][j - 1] \right \}$。这时候发现会超时。

　　这个时候我们改变$f[i][j]$的定义为选择$a[i]$且选择了不超过$j$个物品的最大值，那么就可以得到$f[i][j] = max\left\{f[i - 1][j], f[i - k][j - 1] + a[i]\right\}$

#include <iostream>
#include <cstring>
#define MAXN 10001
#define MAXM 101

using namespace std;

int n, m, k;
int a[MAXN];
int f[MAXN][MAXM];

int main()
{
    cin >> n >> m >> k;
    memset(f, -128, sizeof f);
    for(register int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for(register int i = 1; i <= n; i++)
    {
        f[i][1] = max(f[i - 1][1], a[i]);
        for(register int j = 2; j <= m; j++)
        {
            if(i - k > 0) f[i][j] = max(f[i - 1][j], f[i - k][j - 1] + a[i]);
            else f[i][j] = f[i - 1][j];    
        }
    }
    cout << f[n][m];
    return 0;
}