盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5064 Find Sequence(LIS+dp)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5064

题意

给定n个正整数,这n个数相加为M(0<M≤2^22)。问从这n个数选出一些数,从小到大排序,使得b2-b1≤b3-b2……≤bt-bt-1。求t的最大值

思路

首先考虑解的结构一定是C1,C1……C2,C3……Cm。其中C1<C2<……<Cm。所以可以对ai去重后排序。可以知道此时的ai的个数为sqrt(M)级别的。
然后用dp[i][j]表示以aj结尾,ai为倒数第二个数的最优解。dp[i][j] = max(dp[k][i]) + 1, 其中ai-ak≤aj-ai
这样的复杂度是O(n^3),其中n为1000级别的,会TLE。
发现有一个优化:dp[i][j+1] = max(dp[k][i]) + 1, 其中ai-ak≤aj-ai<aj+1-ai。所以重复的部分只需要计算一次即可。这样复杂度降到O(n^2)

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
const int N = 3000;
int n, m;
int a[N * N], cnt[N], dp[N][N];
void change(int &a, int b) {
if (a < b) a = b;
}
int main () {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
sort(a + 1, a + n + 1);
int cur;
cnt[cur = 1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == a[cur]) cnt[cur]++;
else {
a[++cur] = a[i];
cnt[cur] = 1;
}
}
n = cur;
for (int i = 1; i <= n; i++) dp[i][i] = cnt[i];
int k, res, ans = 0;
for (int i = 1; i <= n; i++) {
k = i;
res = dp[i][i];
change(ans, res);
for (int j = i + 1; j <= n; j++) {
for (; k > 0 && a[i] - a[k] <= a[j] - a[i]; k--) change(res, dp[k][i] + 1);
dp[i][j] = res;
change(ans, res);
}
}
printf("%d\n", ans);
}
return 0;
}