codeforces k-Tree (dp仍然不会耶)

题目 题意: 给定一棵树，每个节点恰好有k个儿子，对应的边恰好为1-k. 求一下有多少种方案，满足路径上的权值恰好为n，且至少有一个边满足边权>=d. 思路: 其实就是个线性dp，每一层只能选1-k.好久没dp就d不出来了，可以先dp一遍1-k都能用的，再dp一遍只能用1-(d-1)的，相减就是满足题意的.f[0][i][j]: 用全部边，从前i层中选，边权恰好为j的方案数。只需枚举当前这一层用多少权值，即可递推出。f[0][i][j] = f[0][i-1][j-1…k] 只依赖于上一层，所以可以把i这一维给压缩掉。f[0][j] = f[0][j-1…k] 时间复杂度: O(n* n * k)或O(n*k) 代码:

#include
using namespace std;
const int N = 102;
const int mod = 1e9+7;
int n,m,k,T;
int f[2][N]; //0:所有边,1:小于d的边,f[j]:权值为j的方案数
void solve()
{
	cin>>n>>k>>m;
	f[0][0] = 1;
		for(int j=1;j