CFR 431 C. k-Tree ( DP )

Problem - C - Codeforces
題意：
給 N, K, D，K 描述一顆樹，其任意一個節點向 K 個子節點有邊，權值分別是 1 至 K 。求有多少由跟出發的路徑，滿足其權值和為 N，且存在至少一個邊其權值不小於 K。
解法：
由於轉移是固定的，且權值和之間狀態具有單調遞增特性，可以考慮動態規劃。
dp[ i ][ j ] : 權值和為 i，已經有一個邊其權值不小於 K。

int N, K, D;

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

void preprocess(){

}

void solve(){
	vvi dp( N + 1, vi( 2 ) );
	dp[ 0 ][ 0 ] = 1;
	for( int i = 0; i < N; ++i )
		for( int j = 0; j < 2; ++j )
			for( int k = 1; k <= K; ++k ){
				if( i + k > N )
					break;
				( dp[ i + k ][ j | k >= D ] += dp[ i ][ j ] ) %= MOD7;
			}
	cout << dp[ N ][ 1 ] << endl;
}