首页 > 代码库 > USACO nocows DP
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。