{DP!}ZOJ 2604

{DP!}ZOJ 2604

这个题的题意给出了很多限制

给出的n是开壶的个数

并且都是成对出现的

dp[i][j]i为n，j为小于等于k

dp[i][1]遍都是一种，都是()()()()()()()()()这种形式

其次会出现(((())))()()()()   ()()()(()()()))()()这种形式

总有一个最大深度的

把第一个看成特殊的！！！

把每一个分成了两种情况(X)Y

推dp[i][j] 的时候就根据这个式子

dp[i][j]  +=    （X的种数）dp[k-1][j-1] * (Y的种数)dp[i-k][j]

其中只要i-k + k-1 + 1的和就为开壶的对数i即可

所以可以对调

/*

dp1 1+=dp0 1dp00 1 += 1 * 1 1 dp2 1+=dp1 1dp00 1 += 1 * 1 1 dp2 1+=dp0 1dp10 1 += 1 * 0 1

*/

n = 52dp = [[1 if i == 0 else 0 for j in range(n)] for i in range(n)]for i in range(1, n): for j in range(1, n): for k in range(1, i + 1): dp[i][j] += dp[i - k][j] * dp[k - 1][j - 1]ri = 0while True: i, j = map(int, raw_input().split()) if i == 0 or j == 0: break if ri > 0: print ri += 1 print ("%s %d: %d" % ('Case', ri, dp[i][j] - dp[i][j - 1]) )

import java.util.*;import java.math.*;public class Main{ static BigInteger dp[][]=new BigInteger[55][55]; public static void f(){ for(int i=0;i<=52;i++) for(int j=0;j<=52;j++) dp[i][j] = BigInteger.ZERO; for(int j=0;j<=52;j++) dp[0][j] = BigInteger.ONE; for(int i=1;i<=52;i++) for(int j=1;j<=52;j++) for(int k=1;k<=i;k++) dp[i][j] = dp[i][j].add( dp[k-1][j-1].multiply(dp[i-k][j]) ); } public static void main(String[] args) { f(); Scanner in = new Scanner(System.in); int kase=0; while(in.hasNext()){ int n=in.nextInt(); int k=in.nextInt(); if(n==0&&k==0) break; if(kase!=0) System.out.println(""); System.out.println("Case "+(++kase)+": "+( dp[n][k].subtract(dp[n][k-1]) ) ); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。