USACO nocows DP

这题没想出来，直接参考了nocow，太弱了= =。

基本思想是动态规划，因为树是递归结构，所以可以递归分成子问题处理。一个树可以看成根加左子树加右子树，所以根据乘法原理，N个节点放成k层的结构等于i个节点放成k - 1层乘以N - i - 1个节点放在k - 1层的积。

令dp[i][j] 为i个节点放j层的最多可能数量，则dp[i][j] = sum{dp[k][j - 1] * dp[i - k - 1][j - 1] + 9901} % 9901

做动规还是没感觉，好忧伤

/*
ID:kevin_s1
PROG:nocows
LANG:C++
*/

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <list>
#include <cmath>

using namespace std;

#define MAXN 210
#define MAXK 110

//thought and method
//type:DP
//dp[i][j] = sum{dp[k][j - 1] * dp[i - 1 - k][j - 1]}
//k in {1,2, ... i - 2}
//result = dp[N][K] - dp[N][K-1]

//gobal variable====
int N, K;
int dp[MAXN][MAXK];
int result;
//==================


//function==========
void DP(){
	memset(dp, 0, sizeof(dp));	
	for(int i = 1; i <= K; i++)
		dp[1][i] = 1;
	for(int j = 1; j <= K; j++){
		for(int i = 3; i <= N; i += 2){
			for(int k = 1; k <= i - 2; k += 2){
				dp[i][j] = ((dp[i][j] + dp[k][j - 1] * dp[i - 1 - k][j - 1]) % 9901);
			}
		}
	}
	result = ((dp[N][K] - dp[N][K - 1] + 9901) % 9901);
}

//==================

int main(){
	freopen("nocows.in","r",stdin);
	freopen("nocows.out","w",stdout);
	cin>>N>>K;
	DP();
	cout<<result<<endl;
	return 0;
}

USACO nocows DP,布布扣,bubuko.com

USACO nocows DP

原文：http://blog.csdn.net/kevin_samuel/article/details/35667765