题目传送门
$Noip2021$ 被 $Dp$ 打爆了，回来开始刷 $Dp$ 的题（一道不会），自闭了…….
Solution
怎么说呢？刚刚看题的时候，就觉得这道题其实就是最长下降子序列的裸题（看到5000的数据，甚至还以为有点水），兴冲冲的开了，写完才发现还要求方案数，仔细想了想，才发现自己只会 $O(n)$ 记录，$O(n ^ 2)$ 枚举， 时间复杂度 $O(n ^ 3)$ ，被打爆了 $QWQ$。
仔细想想（一上午没了），其实这题还是可做，我们设 $f_i$ 为以第 $i$ 项结尾的最长下降子序列的长度，然后 $t_i$ 为构成这类序列（以第 $i$ 项结尾，长度为 $f_i$）的方案数，我们不难发现，如果第 $i$ 项和第 $j$ 项的值相同，那么对于能够接在 $j$ 前面的数，一定能够接在 $i$ 前面，那么我们只需将 $t_j$ 清空，就完成了去重（作者太懒，不想画图）。
代码
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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5005;
int n, k;
int root;
LL f[N];
LL a[N];
LL ans, cnt;
int t[N];
int main()
{
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
scanf("%lld", &a[i]);
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j < i;j ++)
if(a[i] < a[j]) f[i] = max(f[i], f[j] + 1);
if(f[i] == 0) f[i] = 1;
if(ans < f[i]) ans = f[i];
for(int j = 1;j < i;j ++)
{
if(f[i] == f[j] && a[i] == a[j]) t[j] = 0;
if(f[i] == f[j] + 1 && a[i] < a[j]) t[i] += t[j];
}
if(!t[i]) t[i] = 1;
}
for(int i = 1;i <= n;i ++)
if(f[i] == ans) cnt += t[i];
cout << ans << " " << cnt;
return 0;
}
|
双倍经验
题目传送门， 题目一摸一样，只不过卡了高精，但貌似 $double$ 可以卡过去？
代码
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
| #include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5005;
int n, k;
int root;
LL f[N];
LL a[N];
LL ans;
long double cnt;
template <class T>
void write(T x)
{
if(x > 9) write(x / 10);
putchar((x % 10) + '0');
}
double t[N];
int main()
{
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
scanf("%lld", &a[i]);
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j < i;j ++)
if(a[i] < a[j]) f[i] = max(f[i], f[j] + 1);
if(f[i] == 0) f[i] = 1;
if(ans < f[i]) ans = f[i];
for(int j = 1;j < i;j ++)
{
if(f[i] == f[j] && a[i] == a[j]) t[j] = 0;
if(f[i] == f[j] + 1 && a[i] < a[j]) t[i] += t[j];
}
if(!t[i]) t[i] = 1;
}
for(int i = 1;i <= n;i ++)
if(f[i] == ans) cnt += t[i];
cout << ans << " ";
printf("%.0Lf", cnt);
return 0;
}
|