解法一, 暴力 DP, TLE
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, a[N], f[N], ans = 1;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
f[1] = 1;
for (int i = 2; i <= n; ++i) { // 枚举合法序列的最后一个点。
f[i] = 1;
for (int j = 1; j < i; ++j) { // 枚举倒数第二个点。
if (a[i] <= a[j] * 2) {
f[i] = max(f[i], f[j] + 1);
ans = max(ans, f[i]); // 更新答案。
}
}
}
printf("%d\n", ans);
return 0;
}
解法二,贪心
#include <bits/stdc++.h>
using namespace std;
int n, a, f, pa, pf, ans;
int main() {
scanf("%d", &n);
scanf("%d", &pa);
ans = pf = 1;
for (int i = 2; i <= n; ++i) {
scanf("%d", &a); // 枚举合法序列的最后一个点。
// 1. 如果可以接在倒数第二个点之后,直接在其基础上序列长度加 1;
// 因为在所有以当前点为最后一个点的合法序列中,加入点 a[i-1] 对答案(序列长度)只有增益,没有损害。
// 2. 如果不可以接在倒数第二个点之后,因为序列值递增,a[i] 必不可能接在 a[i-1] 更前面的点之后。
f = a <= pa * 2 ? pf + 1 : 1;
ans = max(ans, f);
pa = a, pf = f;
}
printf("%d\n", ans);
return 0;
}
你在 ans = max(ans, f[i]); 后面加个break试试
加了之后其实跟解法二其实是一样的,贪心加 DP
解法2我看不他懂啊,奇奇怪怪的写法,还有 ‘?’:’
就是压缩了一下空间,你可以考虑一下怎么优化你现在的 DP 写法的空间
嗯
pf <=> f[i-1],
pa <=> a[i-1]
dp不会超时啊
不会啊