2/8/2018

Problem: http://codeforces.com/problemset/problem/431/C

Solution: DP. We can generalie the problem into, divided number n as the sum of a couple numbers less than k. All so, one of them must be greater or equal to d.

So, we construct a 2-D dp with 0 or 1 denoting whether there already is one number greater or equal to d as the 2nd dimension.

#include
using namespace std;
int main() {
int n, k, d;
cin >> n >> k >> d;
long long dp[105][2] = {0};
long long mod = 1e9 + 7;
dp[0][0] = 1;
dp[0][1] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (i < j) break;
if (j < d) {
dp[i][0] = (dp[i][0] + dp[i - j][0]) % mod;
dp[i][1] = (dp[i][1] + dp[i - j][1]) % mod;
} else {
dp[i][1] = (dp[i][1] + dp[i - j][0] + dp[i - j][1]) % mod;
}
}
}
cout << dp[n][1];
return 0;
}

### Like this:

Like Loading...

*Related*