蓝桥杯2017年第八届真题-对局匹配

题目

题目链接

题解

动态规划。

题目大意： 在一个具有 n n n个元素的集合中选取尽可能多的数，保证这些数不存在两个数相差为 k k k，求个数。 （题目讲的乱七八糟）

首先，我们统计每个数的个数，c[i]表示有多少个i； 对于每个数，都可以选或者不选，若我们不选数 i − k i-k i−k，则我们可以选数 i i i，也可以不选数 i i i；但若我们选数 i − k i-k i−k，则我们绝不能选数 i i i了。还有一种很奇怪的情况，当数 i i i的个数为0时，我们根本就无法选这个数，因此我们完全可以选数 i − k i-k i−k或者不选数 i − k i-k i−k。

dp[i][0/1]表示数 i i i选或者不选时， i i i的对应位上最多能选个数；0表示不选，1表示选；（这个对应位是我自己起的个名字，下面有讲解） 转移方程： dp[i][0] = max(dp[i-k][0], dp[i-k][1]) dp[i][1] = max(dp[i-k][0], dp[i-k][1]) 当数 i i i的数量为0时 dp[i][1] = dp[i-k][0] + c[i] 当数 i i i的数量不为0时 初始化：我们只要初始化好最前面的 k k k个就可以推出后面的了；前 k k k个数（从集合中出现的最小值开始数k个数）中，若这个数在集合中不存在，则初始化为0，否则初始化为出现次数。 答案：最后 k k k个数（从集合中出现的最大值开始向前数k个数）中，对于每个数选或不选的最大dp值之和。之所以答案是这个，是因为我们要找到0 ~ k-1的对应位上的最大dp值，对这些值累加，这就是我们的答案。

这个对应位，真是不好讲，准确的说并没有很严谨的定义。

i i i的对应位就是 i + k i+k i+k、 i + 2 ∗ k i+2*k i+2∗k、……、 i − k i-k i−k、 i − 2 ∗ k i-2*k i−2∗k、…… 以下面的样例的初始化为例，

10 3
0 0 1 1 3 3 4 6 7 7

初始化前3个，即0、1、2； dp[0][1] = 2, dp[1][1] = 2, dp[2][1] = 0 dp[0][0] = 0, dp[1][0] = 0, dp[2][0] = 0 dp[3][1]保存的是在数1和数3中进行选择，保证最终集合中不能出现两个数相差为3的集合个数最大值； 同理，dp[6]保存的是在数1、数3和数6中进行选择，保证最终集合中不能出现两个数相差为3的集合个数最大值。

代码

#include
using namespace std;
const int N = 100010;
typedef long long ll;

int n, k, mx, mn = N, x;
ll dp[N][2], ans, c[N];

int main()
{
	cin>>n>>k;
	for(int i = 1;i >x, c[x] ++, mx = max(x, mx), mn = min(x, mn);
	
	if(k == 0) { // k为0时特判，答案等于不同数的个数 
		for(int i = mn;i