换根DP-树的最长路径、区间DP-石子合并、状态压缩-最短Hamilton路径、数位DP-234的和（模板）

树的最长路径给定一棵树树中包含 n 个结点编号1~n和 n−1 条无向边每条边都有一个权值。现在请你找到树中的一条最长路径。换句话说要找到一条路径使得路径两端的点的距离最远。注意路径中可以只包含一个点。输入格式第一行包含整数 n。接下来 n−1 行每行包含三个整数 ai,bi,ci表示点 ai 和 bi 之间存在一条权值为 ci 的边。输出格式输出一个整数表示树的最长路径的长度。数据范围1≤n≤10000,1≤ai,bi≤n,−105≤ci≤105输入样例6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7输出样例22import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N20010; //存的是无向边 要乘2 //static int f[][]new int[N][N]; static int d1[]new int[N];//存储以i为根的子树中距离根节点的最长路径 static int d2[]new int[N];//存储以i为根的子树中距离根节点的次长路径 static int s1[]new int[N];//存储以i为根的子树中距离根节点的最长路径所对应的最近的子节点 static int s2[]new int[N];//存储以i为根的子树中距离根节点的次长路径所对应的最近的子节点 static int up[]new int[N];//存储i往上的最长路径 static int n,m; static int id1; static int h[]new int[N]; static int e[]new int[N]; static int ne[]new int[N]; static int w[]new int[N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()); int bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()); add(a,b,c);add(b,a,c); } dfs1(1,-1);//更新每个节点为根的子树中向下的最长路径和次长路径 dfs2(1,-1);//更新每节点往上的最长路径 int resInteger.MIN_VALUE; for (int i 1; i n; i) { resMath.max(res, d1[i]d2[i]); resMath.max(d1[i]up[i], res); } bw.write(res); br.close(); bw.flush(); bw.close(); } static void dfs2(int u,int p){ for (int i h[u]; i 0; ine[i]) { int sone[i]; if(sonp)continue; if(sons1[u]){//是u下面的最长路径所对应节点 up[son]w[i]Math.max(d2[u], up[u]); }else{//其他节点 up[son]w[i]Math.max(d1[u], up[u]); } dfs2(son,u); } } static void dfs1(int u,int p){ for (int i h[u]; i 0; ine[i]) { int sone[i]; if(sonp)continue; dfs1(son,u); if(d1[son]w[i]d1[u]){ //如果发现了一个向下的更长路径首先将之前存储的最长路径更新为次长路径 //然后再更新最长路径 d2[u]d1[u]; s2[u]s1[u]; d1[u]d1[son]w[i]; s1[u]son; }else if(d1[son]w[i]d2[u]){ d2[u]d1[son]w[i]; s2[u]son; } } } static void add(int a,int b,int c){ e[id]b; ne[id]h[a]; w[id]c; h[a]id; } }石子合并设有 N 堆石子排成一排其编号为 1,2,3,…,N。每堆石子有一定的质量可以用一个整数来描述现在要将这 N 堆石子合并成为一堆。每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。例如有 4 堆石子分别为1 3 5 2 我们可以先合并 1、2 堆代价为 4得到4 5 2 又合并 1、2 堆代价为 9得到9 2再合并得到 11总代价为 491124如果第二步是先合并 2、3 堆则代价为 7得到4 7最后一次合并代价为 11总代价为 471122。问题是找出一种合理的方法使总的代价最小输出最小代价。输入格式第一行一个数 N 表示石子的堆数 N。第二行 N 个数表示每堆石子的质量(均不超过 1000)。输出格式输出一个整数表示最小代价。数据范围1≤N≤300输入样例4 1 3 5 2输出样例22代码1dfs版本import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1000; static int n,m; static int a[]new int[N]; static int prefixsum[]new int[N];//前缀和数组 static int f[][]new int[N][N];//f[i][j]表示合并区[i,j]需要的最小价值 static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); prefixsum[i]prefixsum[i-1]a[i]; } for (int l 1; l n; l) { for (int r 1; r n; r) { if(lr)f[l][r]0; else f[l][r]Integer.MAX_VALUE; } } dfs(1,n); bw.write(f[1][n]); br.close(); bw.flush(); bw.close(); } static int dfs(int l,int r){ if(f[l][r]!Integer.MAX_VALUE)return f[l][r]; int costprefixsum[r]-prefixsum[l-1]; for (int i l; i r ; i) { f[l][r]Math.min(f[l][r], dfs(l,i)dfs(i1,r)); } f[l][r]cost; return f[l][r]; } }代码2dp写法import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N1000; static int n,m; static int a[]new int[N]; static int prefixsum[]new int[N];//前缀和数组 static int f[][]new int[N][N];//f[i][j]表示合并区[i,j]需要的最小价值 static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); prefixsum[i]prefixsum[i-1]a[i]; } for (int i 1; i n; i) { for (int j 1; j n; j) { if(ij)continue; else f[i][j]Integer.MAX_VALUE; } } for (int len 2; len n; len) { for (int l 1; l n; l) { int r llen-1; if(rn){ int preprefixsum[r]-prefixsum[l-1]; for (int k l; k r; k) { f[l][r]Math.min(f[l][r],f[l][k]f[k1][r]); } f[l][r]pre; } } } bw.write(f[1][n]); br.close(); bw.flush(); bw.close(); } }最短Hamilton路径给定一张 n 个点的带权无向图点从 0∼n−1 标号求起点 0 到终点 n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。输入格式第一行输入整数 n。接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i 到 j 的距离记为 a[i,j]。对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]≥a[x,z]。输出格式输出一个整数表示最短 Hamilton 路径的长度。数据范围1≤n≤200≤a[i,j]≤107输入样例5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0输出样例18import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N21; static int n,m; static int a[][]new int[1N][N]; static int f[][]new int[1N][N]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); for (int i 0; i n; i) { stnew StringTokenizer(br.readLine()); for (int j 0; j n; j) { a[i][j]Integer.parseInt(st.nextToken()); } } // dp[s][i] 表示当前已经经过了集合 s 中的点且当前在第 i 号点停留的最短路径。 //状态转移对于 dp[s][i]枚举 s 中所有其他点的集合求 dp[s][i] 的最小值。 //假设当前我们已经经过了 {0,3} 号点接下来要去 2 号点便是 dp[{0,3,2}][2] // 其可以从两个位置转移 // dp[{0,3}][0]a[0][2] // dp[{0,3}][3]a[3][2] // 这里的 s 存放的是当前哪些点经过了i 存放的是当前在哪个点。 //但用集合存放太麻烦了因此我们可以用二进制表示 s。用 1 表示经过了0 表示没有经过。 //例如当前走过了 0,2,3 号点用二进制表示便是 (1101)2​。假设当前我们已经经过了 [0,3] 号点接下来要去 2 号点便是 dp[13][2] // 其可以从两个位置转移 // dp[9][0]a[0][2] // dp[9][3]a[3][2] //初始化 for (int i 0; i (1n); i) { for (int j 0; j n; j) { f[i][j]Integer.MAX_VALUE; } } f[1][0]0; for (int i 0; i (1n); i) { for (int j 0; j n; j) { if((i(1j))!0){ int prei-(1j); for (int k 0; k n; k) { if((pre(1k))!0){ if(f[pre][k]!Integer.MAX_VALUE) f[i][j]Math.min(f[pre][k]a[k][j], f[i][j]); } } } } } bw.write(f[(1n)-1][n-1]); br.close(); bw.flush(); bw.close(); } }234的和模板问题描述给定两个正整数 l,rl,r你需要求出求出在 l∼rl∼r 之间所有 22 的和加所有 33 的和加所有 44 的和最终输出这个结果。输入格式输入一行包含 22 个正整数 l,rl,r。输出格式输出 l∼rl∼r 之间所有 22 的和加所有 33 的和加所有 44 的和样例输入12 28样例输出36说明22 出现 1111 次33 出现 22 次44 出现 22 次。评测数据规模1≤l≤r≤1091≤l≤r≤109。代码1dfs写法.超时import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N21; static int n,m; static long f[][]new long[20][100]; static char c[]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); //nInteger.parseInt(st.nextToken()); int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()); long r1dfs((r).toCharArray(), 0,(r).length(), true,0); long r2dfs((l-1).toCharArray(), 0, (l-1).length(), true,0); bw.write((r1-r2)); br.close(); bw.flush(); bw.close(); } static long dfs(char c[],int u,int n,boolean limit,int sum){ //f[u][sum] if(un){ return sum;//sum 是一条路径从根到一个叶子节点上累积的贡献它只代表一个具体数字的 2/3/4 数值和。 } long ans0;//ans 是所有路径成千上万、甚至数亿条的贡献加在一起的总和。 要设置成long int uplimit?c[u]-0:9; for (int i 0; i up; i) { if(i2 || i3 || i4)ansdfs(c, u1, n, limitiup,sumi); else ansdfs(c, u1, n, limitiup,sum); } return ans; } }代码2记忆化搜索import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N21; static int n,m; static long f[][]new long[20][100]; static char c[]; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); //nInteger.parseInt(st.nextToken()); int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()); for (int i 0; i f.length; i) { for (int j 0; j f[0].length; j) { f[i][j]-1; } } long r1dfs((r).toCharArray(), 0,(r).length(), true,0); for (int i 0; i f.length; i) { for (int j 0; j f[0].length; j) { f[i][j]-1; } } long r2dfs((l-1).toCharArray(), 0, (l-1).length(), true,0); bw.write((r1-r2)); br.close(); bw.flush(); bw.close(); } static long dfs(char c[],int u,int n,boolean limit,int sum){ //在当前不受限制limit false的前提下 // 如果我已经从最高位走到了第 u 位u 从 0 开始并且前面这些位中所有 2、3、4 的数值和是 sum // 那么从这一位到最后一位的所有数字它们的 2、3、4 数值的总贡献是多少 if(un){ return sum; } if(!limit f[u][sum]!-1)return f[u][sum]; long ans0; int uplimit?c[u]-0:9; for (int i 0; i up; i) { if(i2 || i3 || i4)ansdfs(c, u1, n, limitiup,sumi); else ansdfs(c, u1, n, limitiup,sum); } if(!limit)f[u][sum]ans; return ans; } }