[NC207751] 牛牛的旅游纪念品

1
2
3
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

牛牛在牛市的旅游纪念商店里面挑花了眼，于是简单粗暴的牛牛决定——买最受欢迎的就好了。

但是牛牛的背包有限，他只能在商店的n个物品里面带m个回去，不然就装不下了。

并且牛牛希望买到的纪念品不要太相似，所以导购小姐姐帮助牛牛把纪念品全部排成了一行，牛牛只需要让选出来要买的m个物品中任意两个的位置差都大于等于k就行了。

现在告诉你这n个物品排成一行之后的受欢迎程度（可能是负数），求牛牛带回去的m个物品的最大欢迎度之和。

输入描述

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

输出描述

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

输入

1
2
4 2 2
2 4 -6 1

输出

1
5

说明

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

题解

题目解析

一道稍微不同的01背包题,我看别人的题解看了好长时间,最后看懂了.

我们先定义一个dp数组:

dp[i][j] 表示前i个物品我们选了j个的最大值

由于这道题存在一个条件:选择的两个物品位置之差必须大于等于k

我们的状态转移方程于是也因此产生了些许变化:

如何理解这个状态转移方程:

  • 当第i个位置不选的时候,自然,前面i-1个位置已经组成j的背包了.
  • 当第i个位置选的时候, (i-k,i)^Z(取整数) 中间的自然不能选,那么我们就可以选前dp[i-k][j](i-k个已经组成j-1的背包的情况的最大值).

当然:i-k可能是负数,那么当i-k为负数的时候,我们干脆用0代替i-k就好.(后面会有详细解释为什么可以这么做)

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define endl "\n"
using namespace std;

typedef long long ll;
const int MAXN = 10000+10;

int a[MAXN],dp[MAXN][110];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) cin >> a[i];
	memset(dp,-0x3f3f3f3f,sizeof(dp));
	for(int i=0;i<=n;i++) dp[i][0] = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			dp[i][j] = max(dp[i-1][j],dp[max(0,i-k)][j-1]+a[i]);
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

Remark

这里详细解释一下:

1
dp[i][j] = max(dp[i-1][j],dp[max(0,i-k)][j-1]+a[i]);

上面这一段代码完全可以写成下面的形式

1
2
3
4
5
6
if(i-k <= 0){
	if(j-1 == 0) dp[i][j] = max(dp[i-1][j],dp[0][0]+a[i]);
	else dp[i][j] = dp[i-1][j];
}else{
    dp[i][j] = max(dp[i-1][j],dp[i-k][j-1]+a[i]);
}

解释一下:

  • 当j-1=0且i-k<0的时候,这个情况可以理解为前面i-1个(小于k)都没选,也就是dp[i-1][0].因为dp[i][0]=dp[0][0]=0所以干脆用0代替了.

  • 当j-1>0且i-k<0的时候,显然不可能出现这样的情况,也就是前面i-1个(小于k)都没选,但又组成了非0的背包.显然这是不可能的.

于是我们把这两个合成一个更简洁.