Algoogle

Algorithm for Programming Contest

Codeforces 431C k-Tree

Category: Codeforces Tag: dp, tree

k-Tree

問題概要


k分木の拡張点から子への各辺の重さをそれぞれ1からkとしたとき
根から少なくとも1つ重さd以上の辺を使ったパスのうち重さの総和がnになるものはいくつか

解法


dp[i][j][k] := 深さiで条件を満たしているかがjのとき, 重さの総和がkになる場合の数
とすれば深さnまで配るDPを繰り返せばよい

コード


(431C.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
const int mod = 1e9+7;
inline int f(int &a, int b){ return a=(a+b)%mod;}
int N, K, D, dp[2][128], ndp[2][128], ans;

int solve(){
    dp[0][0] = 1;
    rep(i,N){
        memset(ndp,0,sizeof(ndp));
        repi(j,1,K+1)rep(k,N-j+1){
            if(j < D) f(ndp[0][k+j],dp[0][k]);
            else f(ndp[1][k+j],dp[0][k]);
            f(ndp[1][k+j],dp[1][k]);
        }
        swap(dp,ndp);
        f(ans,dp[1][N]);
    }
    return ans;
}

void input(){
    cin >> N >> K >> D;
}

int main(){
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    input();
    cout << solve() << endl;
    return 0;
}

Comments