首页 > 代码库 > Codeforces 23E Tree(树型DP)
Codeforces 23E Tree(树型DP)
题目链接 Tree
dp[x][i]表示以x为根的子树中x所属的连通快大小为i的时候 答案最大值
用dp[x][j] * dp[y][k] 来更新dp[x][j + k]。
(听高手说这类题的套路其实都差不多)
因为这题输出数据会很大所以用Java……
QAQ
1 import java.util.*; 2 import java.io.*; 3 import java.math.*; 4 5 public class Main{ 6 static final int maxn = 710; 7 static BigInteger dp[][] = new BigInteger[maxn][maxn]; 8 static int v[][] = new int[maxn][maxn]; 9 static int sum[] = new int[maxn]; 10 static int n; 11 12 static void dfs(int x, int pre){ int y; 13 sum[x] = 1; 14 for(int i = 0; i <= n; ++i) dp[x][i] = BigInteger.ONE; 15 for(int i = 1; i <= v[x][0]; ++i){ 16 y = v[x][i]; 17 if(y == pre) continue; 18 dfs(y, x); 19 for(int j = sum[x]; j >= 0; --j) 20 for(int k = sum[y]; k >= 0; --k){ 21 dp[x][j + k] = dp[x][j + k].max(dp[x][j].multiply(dp[y][k])); 22 } 23 sum[x] += sum[y]; 24 } 25 for(int i = 1; i <= sum[x]; ++i) dp[x][0] = dp[x][0].max(dp[x][i].multiply(BigInteger.valueOf(i))); 26 } 27 28 public static void main(String[] args){ 29 Scanner in = new Scanner(System.in); 30 n = in.nextInt(); 31 for(int i = 1; i <= n; ++i){ 32 v[i][0] = 0; 33 } 34 for(int i = 1; i < n; ++i){ 35 int x = in.nextInt(); 36 int y = in.nextInt(); 37 v[x][++v[x][0]] = y; 38 v[y][++v[y][0]] = x; 39 } 40 dfs(1, 0); 41 System.out.println(dp[1][0]); 42 } 43 44 }
Codeforces 23E Tree(树型DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。