本文主要是介绍Codeforces #247 (Div. 2) C. k-Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意就不说了
我上来就用暴力回溯写了，这几天练暴力练得脑残了
暴力的代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 10010
#define ll long long
using namespace std;int n, k, d;
int maxs, sum;
int a[MAXN];
ll tot;void search(int cur) {if(sum >= n) {if(sum == n) {for(int i=0; i<cur; ++i)maxs = max(maxs, a[i]);
// cout << "maxs = " << maxs << endl;if(maxs>=d && maxs <=k) {tot++;/*for(int i=0; i<cur; ++i) {cout << a[i] << " ";}cout << endl;*/}}maxs = -1;}else {for(int i=1; i<=n; ++i) {a[cur] = i;maxs = max(maxs, i);sum += i;search(cur+1);sum -= i;}}
}int main(void) {while(cin >> n >> k >> d) {sum = 0;tot = 0;maxs = -1;search(0);cout << tot%(1000000007) << endl;}return 0;
}第５个样例就TLE了
今天看别人的代码才看懂
用递推做的
先找到所有和为n，n拆分后的加数最大项小于等于k的情况总个数ans1
然后找到所有和为n, n拆分后的加数最大项小于d的情况总个数ans2
然后输出((ans1-ans2)%(1e9+7)+(1e9+7))%(1e9+7)
代码如下：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAXN 110
#define ll long long
#define MASK 1000000007
using namespace std;ll f1[MAXN][MAXN];
ll f2[MAXN][MAXN];int main(void) {int n, k, d;
// f[i][j]表示把和为j的数拆分成i项有多少种情况while(cin >> n >> k >> d) {memset(f1, 0, sizeof(f1));for(int i=1; i<=k; ++i) {f1[1][i] = 1;}for(int i=2; i<=n; ++i) {for(int j=2; j<=n; ++j) {int t = min(j, k);for(int l=1; l<=t; ++l) {f1[i][j] = (f1[i][j]+f1[i-1][j-l])%MASK;}}}memset(f2, 0, sizeof(f2));for(int i=1; i<d; ++i)f2[1][i] = 1;for(int i=2; i<=n; ++i) {for(int j=2; j<=n; ++j) {int t = min(j, d-1);for(int l=1; l<=t; ++l) {f2[i][j] = (f2[i][j]+f2[i-1][j-l])%MASK;}}}ll ans = 0;for(int i=1; i<=n; ++i) {ans += f1[i][n];// cout << "f1[" << i << "][" << n << "] = " << f1[i][n] << endl;}for(int i=1; i<=n; ++i) {ans -= f2[i][n];// cout << "f2[" << i << "][" << n << "] = " << f2[i][n] << endl;}cout << (ans%MASK+MASK)%MASK << endl;}return 0;
}这篇关于Codeforces #247 (Div. 2) C. k-Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
