数字三角形模板数字三角形题目描述上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径把路径上面的数加起来可以得到一个和你的任务就是找到最大的和路径上的每一步只可沿左斜线向下或右斜线向下走。输入描述输入的第一行包含一个整数 N (1≤N≤100)N (1≤N≤100)表示三角形的行数。下面的 NN 行给出数字三角形。数字三角形上的数都是 00 至 9999 之间的整数。输出描述输出一个整数表示答案。输入输出样例示例输入5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5输出30import 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 N110; static int a[][]new int[N][N]; static int f[][]new int[N][N]; static 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()); for (int j 1; j i; j) { a[i][j]Integer.parseInt(st.nextToken()); } } //f(i,j)表示到顶点(i,j)的最大的和 for (int i 1; i n; i) { for (int j 1; j i; j) { f[i][j]a[i][j]Math.max(f[i-1][j], f[i-1][j-1]); } } int resInteger.MIN_VALUE; for (int i 1; i n; i) { resMath.max(res, f[n][i]); } bw.write(res); br.close(); bw.flush(); bw.close(); } }迪沃斯定理模板问题描述给定一个长度为 nn 的序列 aa你需要输出如下内容第一行输出该序列最长严格上升子序列的长度。第二行输出该序列最少的严格上升子序列的划分个数。第三行输出该序列最长非严格上升子序列的长度。第四行输出该序列最少的非严格上升子序列的划分个数。严格上升对于 ij,aiajij,ai​aj​。非严格上升对于 ij,ai≤ajij,ai​≤aj​。最少的严格上升子序列的划分个数对于一个子序列其最少可以划分成几个严格上升子序列。例如 [3,1,2,2,3][3,1,2,2,3]我们最少可以划分成 [3],[1,2],[2,3][3],[1,2],[2,3]。输入格式第一行输入一个正整数 nn。(1≤n≤1000)(1≤n≤1000)第二行输入 nn 个整数表示序列 aa。(1≤ai≤100,1≤i≤n)(1≤ai​≤100,1≤i≤n)输出格式第一行输出该序列最长严格上升子序列的长度。第二行输出该序列最少的严格上升子序列的划分个数。第三行输出该序列最长非严格上升子序列的长度。第四行输出该序列最少的非严格上升子序列的划分个数。样例输入10 1 4 7 3 6 8 1 3 4 4样例输出4 4 5 3提示根据迪沃斯定理最长严格上升子序列最少划分数 最长非严格下降子序列的长度。最长非严格上升子序列的最少划分数 最长严格下降子序列的长度。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 N1010; static int a[]new int[N]; static int f[]; static 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()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //f(i)表示以i结尾的最长严格上升子序列的长度 fnew int[n1]; for (int i 1; i n; i) { f[i]1; for (int j i-1; j 0; j--) { if(a[j]a[i]){ f[i]Math.max(f[i], f[j]1); } } } int r11; for (int i 1; i n; i) { r1Math.max(r1, f[i]); } bw.write(r1\n); //f(i)表示以i结尾的最长不严格下降子序列的长度 fnew int[n1]; for (int i 1; i n; i) { f[i]1; for (int j i-1; j 0; j--) { if(a[j]a[i]){ f[i]Math.max(f[i], f[j]1); } } } int r21; for (int i 1; i n; i) { r2Math.max(r2, f[i]); } bw.write(r2\n); //f(i)表示以i结尾的最长不严格上升子序列的长度 fnew int[n1]; for (int i 1; i n; i) { f[i]1; for (int j i-1; j 0; j--) { if(a[j]a[i]){ f[i]Math.max(f[i], f[j]1); } } } int r31; for (int i 1; i n; i) { r3Math.max(r3, f[i]); } bw.write(r3\n); //f(i)表示以i结尾的最长严格下降子序列的长度 fnew int[n1]; for (int i 1; i n; i) { f[i]1; for (int j i-1; j 0; j--) { if(a[j]a[i]){ f[i]Math.max(f[i], f[j]1); } } } int r41; for (int i 1; i n; i) { r4Math.max(r4, f[i]); } bw.write(r4\n); br.close(); bw.flush(); bw.close(); } }翻转后1的数量2星问题描述现在有一个 00 和 11 构成的长度为 nn 的子符串 SS你可以对 SS 串进行至多一次操作操作具体为选择 SS 串中的一个区间将该区间所有的字符翻转问在经过至多一次操作后 SS 串中 11 的数量最多可以为多少翻转0→1,1→00→1,1→0。输入格式第一行输入一个正整数 nn表示字符串的长度。第二行输入长度为 nn 的字符串 SS。输出格式输出一个整数表示 11 的数量最大值。样例输入5 00101样例输出4说明选择区间 [1,2][1,2] 进行翻转SS 串成为11101有 44 个 11。评测数据规模1≤n≤1051≤n≤105。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 N100010; static int f[][]new int[N][3]; static 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()); char s[]( br.readLine()).toCharArray(); //我们定义状态f(i,0)为到当前i为止时未经过翻转的一的最大数量 //我们定义状态f(i,1)为到当前i为止时正要翻转的一的最大数量 //我们定义状态f(i,2)为到当前i位置时停止翻转的一的最大数量 //f(i,0)f(i-1,0)x-0 //f(i,1)max(f(i-1,0)f(i-1,1))(x^1)-0 ^表示异或 (x^1)可以讲当前位置取反 这里是ASCII码的取反 //f(i,2)max(f(i-1,1),f(i-1,2))x-0 //该位置不能是0 for (int i 1; i n; i) { char xs[i]; f[i][0]f[i-1][0](x-0); f[i][1]Math.max(f[i-1][0], f[i-1][1])((x^1)-0); if(i!1)f[i][2]Math.max(f[i-1][1], f[i-1][2])(x-0); } int resMath.max(Math.max(f[n][0], f[n][1]),f[n][2]); bw.write(res); br.close(); bw.flush(); bw.close(); } }最长公共子序列题目描述给定一个长度为 NN 数组 aa 和一个长度为 MM 的数组 bb。请你求出它们的最长公共子序列长度为多少。输入描述输入第一行包含两个整数 N,MN,M分别表示数组 aa 和 bb 的长度。第二行包含 NN 个整数 a1,a2,...,ana1​,a2​,...,an​。第三行包含 MM 个整数 b1,b2,...,bnb1​,b2​,...,bn​。1≤N,M≤1031≤N,M≤1031≤ai,bi≤1091≤ai​,bi​≤109。输出描述输出一行整数表示答案。输入输出样例示例 1输入5 6 1 2 3 4 5 2 3 2 1 4 5输出4运行限制最大运行时间1s最大运行内存: 128Mimport 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 N1010; static int a[]new int[N]; static int b[]new int[N]; static int f[][]new int[N][N]; static 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()); int mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } stnew StringTokenizer(br.readLine()); for (int i 1; i m; i) { b[i]Integer.parseInt(st.nextToken()); } //f[i][j]定义为以a中i下标结尾 b中j下标结尾 的 最长公共子序列长度 for (int i 1; i n; i) { for (int j 1; j m; j) { if(a[i]b[j])f[i][j]f[i-1][j-1]1; else f[i][j]Math.max(f[i][j-1],f[i-1][j]); } } bw.write(f[n][m]); br.close(); bw.flush(); bw.close(); } }最长上升子序列给定一个长度为 N 的数列求数值严格单调递增的子序列的长度最长是多少。输入格式第一行包含整数 N。第二行包含 N 个整数表示完整序列。输出格式输出一个整数表示最大长度。数据范围1≤N≤100000−109≤数列中的数≤109输入样例7 3 1 2 1 8 5 6输出样例4import 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 N100010; static int a[]new int[N]; static int f[]new int[N]; static 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()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //定义f[i]为长度为i的严格单调递增的子序列末尾最小的数 //定义为最小的数 是因为相等于是贪心策略 为后续更长的子序列做基础 //依次加进去的数保持单调递增 若当前的数小于f最后一个元素则在f中找到第一个大于等于我的数将其替换 //最后f的长度就是答案 int len0;//f的长度 for (int i 1; i n; i) { if(len0 || f[len-1]a[i])f[len]a[i]; else{ int idxfindMax(a[i],len-1); f[idx]a[i]; } } // for (int i 1; i n; i) { // bw.write(f[i] ); // } // bw.write(\n); bw.write(len); br.close(); bw.flush(); bw.close(); } static int findMax(int u,int n){ int l0,rn; while(lr){ int mid(lr)1; if(f[mid]u)rmid; else lmid1; } return l; } }