Posted in Dynamic Programming

CF 431C k-Tree

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;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s