AcWing 3583. 整数分组
原题链接
中等
作者:
ITNXD
,
2021-05-29 11:03:38
,
所有人可见
,
阅读 287
详细请查看注释内容
参考代码:
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5010;
/*
状态表示:f[i][j]表示只从前i个数中选且分j组的集合!属性:最大能选多少个数!
状态计算:
不选i:f[i - 1][j]
选 i:f[k - 1][j - 1] + i - k + 1 (k为选i的一组的差值小于5最靠左的下标,i - k + 1为选i最后一组的元素个数)
因此:f[i][j] = max(f[i - 1][j], f[k - 1][j - 1] + i - k + 1)
最终答案:f[n][m],m为最大组数,即使最优解不是分为m组,我们也可以将其拆分为m组,最大可选数并不会改变!
关于如何快速求选i的最后一组差值小于5的最靠左的下标,可以使用双指针扫描:
1. 该序列为排序好的序列,具有单调性!
2. i 往前走 k 一定往后走!
*/
int f[N][N], w[N];
int main(){
int n, m; cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> w[i];
sort(w + 1, w + n + 1);
// 双指针求k
for(int i = 1, k = 1; i <= n; i ++){
while(w[i] - w[k] > 5) k ++;
for(int j = 1; j <= m; j ++)
f[i][j] = max(f[i - 1][j], f[k - 1][j - 1] + i - k + 1);
}
cout << f[n][m] << endl;
return 0;
}