题解 | #牛牛的旅游纪念品#

牛牛的旅游纪念品

题目描述

牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。 但是牛牛的背包有限，他只能在商店的n个物品里面带m个回去，不然就装不下了。 并且牛牛希望买到的纪念品不要太相似，所以导购小姐姐帮助牛牛把纪念品全部排成了一行，牛牛只需要让选出来要买的m个物品中任意两个的位置差都大于等于k就行了。 现在告诉你这n个物品排成一行之后的受欢迎程度（可能是负数），求牛牛带回去的m个物品的最大欢迎度之和。

输入描述

第一行三个数n,m,k

接下来一行,有n个整数,是n个物品按顺序的受欢迎程度。

输出描述

输出一个数为题目所求的最大和

数据范围

n≤10000,m≤100，m≤n，答案保证在int范围内，保证按照题目要求一定能取到m个物品

解析

我先来讲一下我最开始的想法：

解法一（会超时）

状态表示

f[i][j]表示在前j个纪念品中选i个，并且第i个选的是a[j]

状态计算

f[i][j] = max(f[i][j],f[i - 1][x] + a[j])，其中x表示第i - 1件纪念品可以选的范围，因为每两件纪念品之间的间隔要大于k，则第i件纪念品可以在的位置最小为(i - 1) * (k - 1) + i，这个大家可以自行去验证哈，我就不在这里验证了。这里是以第i - 1件物品为分界线，来对状态进行分类。其实个人认为这个方法更好理解一些，但是他超时了呜呜呜呜呜呜呜，大家可以看一下我的代码，有其他想法可以在评论区告诉我喔~

#include <bits/stdc++.h>

using namespace std;
const int N = 10010;
int n,m,k,a[N],f[110][N];//f[i][j]表示前j个里面选i个，并且第i个选的是a[j]

int main()
{
    cin >> n >> m >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++){
        f[1][i] = a[i];
    }
    for(int i = 2;i <= m;i ++){//选i个
        for(int j = k + 1;j <= n;j ++){
            for(int x = max(1,i * k - 2 * k + 1);x <= j - k;x ++){
                f[i][j] = max(f[i][j],f[i - 1][x] + a[j]);
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        ans = max(ans,f[m][i]);
    }
    cout << ans << '\n';
    return 0;
}

解法二（正确解法）

状态表示

f[i][j]表示在前i件纪念品中选j个（选的第j件纪念品不一定是a[i]）

状态计算

f[i][j]可以由以下两种状态转移过来：

（1）没有买a[i]，那么f[i][j] = f[i - 1][j]

（2）买了a[i]，那么f[i][j] = f[i - k][j - 1] + a[i]

最开始要对f[i][j]进行初始化，f[i][1]表示在前i件纪念品中选一个，那么f[i][1]一定等于前i件纪念品中受欢迎值最大的那个，f[i][1] = max(f[i - 1][1],a[i])

#include <bits/stdc++.h>

using namespace std;
const int N = 10010;
int n,m,k,a[N],f[N][110];//f[i][j]表示前i个里面选j个，并且第i个选的是a[j]

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