动态规划-数字三角形（模板）、迪沃斯定理（模板）、翻转后1的数量（2星）、最长公共子序列、最长上升子序列
数字三角形（模板）
数字三角形
题目描述
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。
输入描述
输入的第一行包含一个整数 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 N=110; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); for (int i = 1; i <= n; i++) { st=new 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 res=Integer.MIN_VALUE; for (int i = 1; i <= n; i++) { res=Math.max(res, f[n][i]); } bw.write(res+""); br.close(); bw.flush(); bw.close(); } }迪沃斯定理（模板）
问题描述
给定一个长度为 nn 的序列 aa，你需要输出如下内容：
第一行输出该序列最长严格上升子序列的长度。
第二行输出该序列最少的严格上升子序列的划分个数。
第三行输出该序列最长非严格上升子序列的长度。
第四行输出该序列最少的非严格上升子序列的划分个数。
严格上升：对于 i<j,ai<aji<j,ai<aj。
非严格上升：对于 i<j,ai≤aji<j,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 N=1010; static int a[]=new int[N]; static int f[]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //f(i)表示以i结尾的最长严格上升子序列的长度 f=new int[n+1]; 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 r1=1; for (int i = 1; i <= n; i++) { r1=Math.max(r1, f[i]); } bw.write(r1+"\n"); //f(i)表示以i结尾的最长不严格下降子序列的长度 f=new int[n+1]; 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 r2=1; for (int i = 1; i <= n; i++) { r2=Math.max(r2, f[i]); } bw.write(r2+"\n"); //f(i)表示以i结尾的最长不严格上升子序列的长度 f=new int[n+1]; 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 r3=1; for (int i = 1; i <= n; i++) { r3=Math.max(r3, f[i]); } bw.write(r3+"\n"); //f(i)表示以i结尾的最长严格下降子序列的长度 f=new int[n+1]; 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 r4=1; for (int i = 1; i <= n; i++) { r4=Math.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 N=100010; static int f[][]=new int[N][3]; static int n; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.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 x=s[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 res=Math.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≤103，1≤ai,bi≤1091≤ai,bi≤109。
输出描述
输出一行整数表示答案。
输入输出样例
示例 1
输入
5 6 1 2 3 4 5 2 3 2 1 4 5输出
4运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
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 N=1010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); int m=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } st=new 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 N=100010; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 1; i <= n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //定义f[i]为长度为i的严格单调递增的子序列末尾最小的数 //定义为最小的数 是因为相等于是贪心策略 为后续更长的子序列做基础 //依次加进去的数保持单调递增 若当前的数小于f最后一个元素，则在f中找到第一个大于等于我的数将其替换 //最后f的长度就是答案 int len=0;//f的长度 for (int i = 1; i <= n; i++) { if(len==0 || f[len-1]<a[i])f[len++]=a[i]; else{ int idx=findMax(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 l=0,r=n; while(l<r){ int mid=(l+r)>>1; if(f[mid]>=u)r=mid; else l=mid+1; } return l; } }