题意: 给出 K-Tree 定义, 每个结点都有恰好 K 个孩子每个节点到它 K 个孩子的 K 条边的权重刚好是 1,2,3...,K 然后问你总权值为 n 的路有多少条
思路: 个人感觉有点像背包一样, 因为转移的是价值, 感觉之歌状态定义的很巧妙, 如果能定义出来, 估计自己也能做出来, 这个题还有一个巧妙的地方是把低于 d 的路转化为全部小于权值 d 的, 是一个容斥, 这个容斥很棒, 不好想 (反正我是不行)
代码:
- #include < bits / stdc++.h > using namespace std;
- typedef long long LL;
- const int MOD = 1e9 + 7;
- LL dp[2][105];
- int n,
- k,
- d;
- int main() {
- scanf("%d%d%d", &n, &k, &d);
- d--;
- memset(dp, 0, sizeof(dp));
- dp[0][0] = 1;
- dp[1][0] = 1;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= k; j++) {
- if (i - j < 0) break;
- dp[0][i] = (dp[0][i - j] + dp[0][i]) % MOD;
- }
- for (int j = 1; j <= d; j++) {
- if (i - j < 0) break;
- dp[1][i] = (dp[1][i] + dp[1][i - j]) % MOD;
- }
- }
- printf("%I64d\n", ((dp[0][n] - dp[1][n]) % MOD + MOD) % MOD);
- return 0;
- }
- CodeForces 431C k-Tree
来源: http://www.bubuko.com/infodetail-2501695.html