请你使用c++完成下面的问题:有一棵树,每个节点都有n个儿子,每个节点到它的儿子的距离依次为a1到an。问有多少点到根的距离小于等于k,这个数可能会很大,输出模1000000007的结果即可。
时间: 2024-03-14 14:47:55 浏览: 16
下面是使用 C++ 代码实现该问题的解决方案:
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n, k;
int a[maxn], dp[maxn];
int main()
{
cin >> n >> k;
dp[0] = 1;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
for(int j = i; j >= 1; j--)
{
if(a[i] + dp[j-1] > k) break;
dp[j] = (dp[j] + dp[j-1] * a[i]) % mod;
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
ans = (ans + dp[i]) % mod;
cout << ans << endl;
return 0;
}
```
算法思路:
1. 动态规划
定义 $dp_{i,j}$ 表示以第 $i$ 个节点为根的子树中,有多少个节点到根的距离不超过 $j$。
初始状态:$dp_{0,0}=1$,表示空树的根节点到根节点的距离是 $0$。
状态转移:假设当前节点为 $i$,当前节点到其父亲节点的距离为 $a_i$,则有:
$$dp_{i,j}=\sum_{k=0}^{j-1} dp_{i-1,k} \times a_i$$
其中,$j \in [a_i, k]$,表示当前节点到根节点的距离必须不超过 $k$ 才能被计算。
时间复杂度:$O(n^2)$
2. 优化
观察到状态转移方程中,$dp_{i-1,k}$ 与 $dp_{i,j}$ 有关,且 $k<j$,因此可以从后往前更新,这样可以保证 $dp_{i-1,k}$ 在更新 $dp_{i,j}$ 时仍然是上一轮的值。
时间复杂度:$O(n^2)$ -> $O(n)$
3. 进一步优化
由于每次更新的 $dp_{i,j}$ 都是 $dp_{i-1}$ 中的某个值 $dp_{i-1,k}$ 乘以 $a_i$ 而来,因此可以直接使用一个一维数组存储 $dp_{i-1}$,每次更新时从后往前更新,这样就可以节省空间。
时间复杂度:$O(n)$,空间复杂度:$O(n)$
最终代码实现:
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)