Codeforces 23E Tree（树型DP）

题目链接 Tree

$dp[x][i]$表示以x为根的子树中x所属的连通快大小为i的时候答案最大值

用$dp[x][j]$ * $dp[y][k]$ 来更新$dp[x][j + k]$。

（听高手说这类题的套路其实都差不多）

因为这题输出数据会很大所以用Java……

QAQ

import java.util.*;

import java.io.*;

import java.math.*;

public class Main{

    static final int maxn = 710;

    static BigInteger dp[][] = new BigInteger[maxn][maxn];

    static int v[][] = new int[maxn][maxn];

    static int sum[] = new int[maxn];

    static int n;

    static void dfs(int x, int pre){ int y;

        sum[x] = 1;

        for(int i = 0; i <= n; ++i) dp[x][i] = BigInteger.ONE;

        for(int i = 1; i <= v[x][0]; ++i){

            y = v[x][i];

            if(y == pre) continue;

            dfs(y, x);

            for(int j = sum[x]; j >= 0; --j)

                for(int k = sum[y]; k >= 0; --k){

                    dp[x][j + k] = dp[x][j + k].max(dp[x][j].multiply(dp[y][k]));

            }

            sum[x] += sum[y];

        }

        for(int i = 1; i <= sum[x]; ++i) dp[x][0] = dp[x][0].max(dp[x][i].multiply(BigInteger.valueOf(i)));

    }

    public static void main(String[] args){

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        for(int i = 1; i <= n; ++i){

            v[i][0] = 0;

        }

        for(int i = 1; i < n; ++i){

            int x = in.nextInt();

            int y = in.nextInt();

            v[x][++v[x][0]] = y;

            v[y][++v[y][0]] = x;

        }

        dfs(1, 0);

        System.out.println(dp[1][0]);

    }

}

巴特西

Codeforces 23E Tree（树型DP）

最新文章

热门文章