C/C++教程

CF23E Tree(树形DP+高精度)

本文主要是介绍CF23E Tree(树形DP+高精度),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

码了一晚上高精度,结果还被卡内存了。。。

比较裸的树形DP,高精度太恶心了。

最后换成JAVA大数,一发过了。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    public static BigInteger f[][][];
    public static int sz[];
    public static List g[];
    public static int ed[];
    public static void solve (int u,int pre) {
        sz[u] = 1;
        int ff = 1;
        for (int i=0;i<=sz[u];i++) f[0][u][i] = new BigInteger("0");
        f[0][u][1] = new BigInteger("1");
        for (int k=0;k<g[u].size();k++) {
           int v = (int) g[u].get(k);
           if (v == pre) continue;
           solve(v,u);
           sz[u]+=sz[v];
           for (int i=0;i<=sz[u];i++) f[ff][u][i]=new BigInteger("0");
           for (int i=1;i<=sz[u];i++) {
               for (int j=1;j<=sz[v];j++) {
                   if (j>=i) break;
                   if (i-j>sz[u]-sz[v]) continue;
                   f[ff][u][i]=f[ff][u][i].max(f[ff^1][u][i-j].divide(BigInteger.valueOf(i-j)).multiply(BigInteger.valueOf(i)).multiply(f[ed[v]][v][j]).divide(BigInteger.valueOf(j)));
               }
               if (i>sz[u]-sz[v]) continue;
               for (int j=1;j<=sz[v];j++) {
                   f[ff][u][i]=f[ff][u][i].max(f[ff^1][u][i].multiply(f[ed[v]][v][j]));
               }
           }
 
           ff^=1;
        }
        ed[u]=(ff^1);
    }
    public static void main (String []args) {
        f = new BigInteger[2][705][705];
        sz = new int[705];
        g = new List[705];
        ed = new int[705];
        for (int i=0;i<705;i++) g[i] = new ArrayList<Integer>();
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        for (int i=1;i<n;i++) {
            int x=in.nextInt();
            int y=in.nextInt();
            g[x].add(y);
            g[y].add(x);
        }
        solve(1,0);
        BigInteger ans = new BigInteger("0");
        for (int i=1;i<=n;i++) ans=ans.max(f[ed[1]][1][i]);
        System.out.println(ans);
    }
}
这篇关于CF23E Tree(树形DP+高精度)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!