题目描述
对给定数列分成m组,每组内任意两个数相差不超过5,求分组后数最多的方案数值.
ysDP
算法思路
首先考虑找到问题的性质,dp是线性的递推,我们要通过问题的性质把集合->序列.
1.每次选择的组内是连续的.假设选择某一组数值的两端为[l,r],那么在区间中间
的数都是可以选择的(这里的数列已排好序),题目要求最多所以我们能选则选.
2.每个区间可以是独立的.假设某个最优解有两个区间连在一起,我们可以在中间
找到一个端点划分给某一组.
3.每次选择的最右端的区间可以取尽可能长(符合条件的最长).越长这个区间内
的数越多;如果与之前选择的区间有重叠部分,我们可以把重叠部分划分给最右端的区间.
连续;无交集;最后一段尽可能长.有这些性质的区间是一种最优解.利用这几个性质
我们就可以用ysDP分析了。
dp
状态表示:
dp[i][j]
集合:选择前i个数分成j组的所有选择方案
属性:Max
状态划分:
可以以a[i]选/不选作为划分依据.
不选a[i],那么问题变为求选前i-1个物品分成j组的最大方案,根据我们对
状态的定义:dp[i-1][j]
选择a[i],我们最远可以选到a[k],确定的部分:选择了a[k]~a[i];可变部分:
选前k-1个物品分成j-1组.为满足Max属性可变部分要取最大,根据我们对状态的定义
dp[k-1][j-1].
时间复杂度
状态个数 * 状态转移 = O(n*k)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5010;
int n, m;
int a[N];
int dp[N][N];
int main()
{
cin >> n >> m;
for( int i = 1; i <= n; i++ ) cin >> a[i];
sort(a+1,a+n+1);
for( int i = 1, k = 1; i <= n; i++ )
{
while( a[i] - a[k] > 5 ) k++;
for( int j = 1; j <= m; j++ )
{
dp[i][j] = max( dp[i-1][j], dp[k-1][j-1] + (i - k + 1 ));
}
}
printf("%d\n",dp[n][m]);//最优解可以分成m组(<m可以再划分)
return 0;
}