首页 > 代码库 > UVALive 3516 Exploring Pyramids 区间dp+计数原理
UVALive 3516 Exploring Pyramids 区间dp+计数原理
题目链接:点击打开链接
给定多叉树的先序遍历结果,求多叉树的同构数
思路:区间dp
import java.io.PrintWriter; import java.util.ArrayList; import java.util.Scanner; public class Main { int min(int a,int b){return a>b?b:a;} int max(int a,int b){return a>b?a:b;} long min(long a,long b){return a>b?b:a;} long max(long a,long b){return a>b?a:b;} int abs(int x){return x>0?x:-x;} static long mod = 1000 * 1000 * 1000; static int N = 1005; String s; long[][] dp = new long[N][N]; long dfs(int l, int r){ if(dp[l][r]!=-1)return dp[l][r]; if(l == r)return dp[l][r] = 1; if(s.charAt(l)!=s.charAt(r))return dp[l][r] = 0; dp[l][r] = 0; for(int i = l+2; i <= r; i++) if(s.charAt(i) == s.charAt(l)) dp[l][r] += dfs(l+1, i-1)*dfs(i,r)%mod; dp[l][r] %= mod; return dp[l][r]; } void work() { while(cin.hasNext()){ s = cin.next(); for(int i = 0; i <= s.length(); i++) for(int j = i; j <= s.length(); j++) dp[i][j] = -1; out.println(dfs(0, s.length()-1)); } } Main() { cin = new Scanner(System.in); out = new PrintWriter(System.out); } public static void main(String[] args) { Main e = new Main(); e.work(); out.close(); } public Scanner cin; public static PrintWriter out; }
UVALive 3516 Exploring Pyramids 区间dp+计数原理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。