本次训练相关参考资料:

        java动态规划

       石子合并(环形) 

        LCS（最长公共子串和最长公共子序列）java实现

        背包问题汇总-01背包、完全背包、多重背包-java

        循环数组最大子段和

目录

A - 上台阶2

B - 数字三角形 

 C - 矩阵取数问题

D - 背包问题     

E - 完全背包

F - 背包问题 V2

G - 最长上升子序列

H - 最长公共子序列Lcs

I - 石子合并

J - 循环数组最大子段和

K - 没有上司的舞会

L - 滑雪

A - 上台阶2

        小瓜想走上一个一共有n级的台阶，由于小瓜的腿长比较特殊，他一次只能向上走1级或者3级或者5级台阶。小瓜想知道他有多少种方法走上这n级台阶，你能帮帮他吗？

Input

        一行一个整数n（n<=100000），表示一共有n级台阶。

Output

        一行一个整数，表示小瓜上台阶的方案数*对100003取余*的结果。

Sample

3

2

        题解 :DP(动态规划)

import java.util.Scanner;
public class Test01 {//上台阶2static int mod=100003;//定义余数100003public static void main(String[] args) {Scanner cin=new Scanner(System.in);int n=cin.nextInt();int dp[]=new int[n+1];//dp[i]表示i级台阶可以走的方法个数for (int i=3;i<=n;i++){dp[0]=1;dp[1]=1;dp[2]=1;if (i<5){//如果台阶级数小于5时dp[i]=(dp[i-1]+dp[i-3])%mod;}else {//如果台阶级数大于等于3且小于5时dp[i]=(dp[i-1]+dp[i-3]+dp[i-5])%mod;}}System.out.println(dp[n]);//最终输出n级台阶可以走的方法总数}
}

B - 数字三角形 

7
3   8
8   1   0
2   7   4   4
4   5   2   6   5(图1)

        图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

        注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

Input

        输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

Output

        输出最大的和。

Sample

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

30

        题解: DP(动态规划)

import java.util.Scanner;public class Test02 {//数字三角形public static void main(String[] args) {Scanner cin=new Scanner(System.in);int N=cin.nextInt();int dp[][]=new int[N][N];//dp[i][j]表示从起点到达第i行第j列的位置时的最大路径和for (int i=0;i<N;i++){for (int j=0;j<=i;j++){dp[i][j]=cin.nextInt();}}for(int i = N - 1;i > 0;i--){for(int j = 0;j < i;j++){dp[i - 1][j] += Math.max(dp[i][j], dp[i][j + 1]);//由于是下三角,则可以从下往上进行计算最大路径和,dp[0][0]表示的即为所求最大路径和}}System.out.println(dp[0][0]);}
}

 C - 矩阵取数问题

        一个N*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，从左上走到右下，只能向下向右走，求能够获得的最大价值。

        例如：3 * 3的方格。

        1 3 3

        2 1 3

        2 2 1

        能够获得的最大价值为：11。

Input

        第1行：N，N为矩阵的大小。(2 <= N <= 500) 第2 - N + 1行：每行N个数，中间用空格隔开，对应格子中奖励的价值。（1 <= N[i] <= 10000)

Output

        输出能够获得的最大价值。

Sample

3
1 3 3
2 1 3
2 2 1

11

        题解 :DP(动态规划)

import java.util.Scanner;public class Test03 {//矩阵取数问题public static void main(String[] args) {Scanner cin=new Scanner(System.in);int N=cin.nextInt();int dp[][]=new int[N][N];//dp[i][j]表示第i行第j列的位置当前获得的最大价值for (int i=0;i<N;i++){for (int j=0;j<N;j++){dp[i][j]=cin.nextInt();}}int max1=0;//定义一个max1用来更新最大值for (int i=0;i<N;i++){for (int j=0;j<N;j++){//考虑极端情况，分情况讨论if (i==0&&j!=0){dp[i][j]+=dp[i][j-1];}else if (j==0&&i!=0){dp[i][j]+=dp[i-1][j];}else if (i==0&&j==0){dp[i][j]=dp[0][0];}else {dp[i][j]+=Math.max(dp[i-1][j],dp[i][j-1]);}if(i==N-1){//如果是最后一行说明表示已经走到底，可以进行更新最大值max1=Math.max(dp[i][j],max1);}}}System.out.println(max1);}
}

D - 背包问题     

        在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。

        其中1 <= N <= 100，1 <= W <= 10000，每个物品1 <= Wi, Pi <= 10000。

Input

        第1行输入两个整数N和W； 第2 ~ N+1行，每行两个整数Wi和Pi，分别表示每个物品的体积和价值。

Output

        输出可以容纳的最大价值。

Sample

3 6
2 5
3 8
4 9

14

        题解： DP（动态规划)

import java.util.Scanner;public class Test04 {//背包问题public static void main(String[] args) {Scanner cin=new Scanner(System.in);//经典的0-1背包问题int N=cin.nextInt();int M=cin.nextInt();int W[]=new int[N+1];int P[]=new int[N+1];for (int i=1;i<=N;i++){W[i]=cin.nextInt();P[i]=cin.nextInt();}int F[][]=new int[N+1][M+1];//F[i][j]表示为放入i个物品和容积有j的情况时的最大价值for (int i=1;i<=N;i++){for (int j=0;j<=M;j++){F[i][j]=F[i-1][j];if (j>=W[i]){//如果能装下当前物品，则进行比较选出最大值并更新F[i][j]F[i][j]=Math.max(F[i][j],F[i-1][j-W[i]]+P[i]);}}}int max=0;//从放入N个物品，不同容积的背包中筛选出最大价值即为题解for (int i=0;i<=M;i++){max=Math.max(max,F[N][i]);}System.out.println(max);}
}

E - 完全背包

        有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是v[i]，价值是c[i]。

        现在请你选取一些物品装入背包，使这些物品的体积总和不超过背包容量，且价值总和最大。

        其中1<=N<=100，1<=V<=50000，1<=v[i],c[i]<=10000。

Input

        第一行输入两个数N,V，分别表示物品种类数和背包容积； 之后N行，每行两个数v[i],c[i]，分别表示第i种物品的体积和价值；

Output

        输出一个数，表示最大的价值

Sample

2 11
2 3
6 14

20

        题解:DP（动态规划) 

import java.util.Scanner;public class Test05 {//完全背包public static void main(String[] args) {Scanner cin=new Scanner(System.in);int N=cin.nextInt();int V=cin.nextInt();int v[]=new int[N+1];int c[]=new int[N+1];int dp[]=new int[V+1];//dp[i]表示容积为i的背包的最大价值for (int i=1;i<=N;i++){v[i]=cin.nextInt();c[i]=cin.nextInt();}for (int i=1;i<=N;i++){for (int j=v[i];j<=V;j++){dp[j]=Math.max(dp[j],dp[j-v[i]]+c[i]);//进行更新最大价值}}System.out.println(dp[V]);//最终容积为V的背包则为题解的最大价值}
}

F - 背包问题 V2

        有N种物品，每种物品的数量为C1，C2......Cn。从中任选若干件放在容量为W的背包里，每种物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数）。求背包能够容纳的最大价值。

        其中1 <= N <= 100，1 <= W <= 50000，1 <= Wi, Pi <= 10000， 1 <= Ci <= 200。

Input

        第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。 第2 ~ N+1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。

Output

        输出可以容纳的最大价值。

Sample

3 6
2 2 5
3 3 8
1 4 1

9

        题解: DP(动态规划)

import java.util.Scanner;public class Test06 {//背包问题 V2(多重背包)public static void main(String[] args) {// TODO Auto-generated method stubScanner cin=new Scanner(System.in);int N=cin.nextInt();int M=cin.nextInt();int w[]=new int[N+1];//体积数组int v[]=new int[N+1];//价值数组int c[]=new int[N+1];//数量数组for(int i=1;i<=N;i++){w[i]=cin.nextInt();v[i]=cin.nextInt();c[i]=cin.nextInt();}int dp[]=new int[M+1];//dp[i]表示容积为i的背包的最大价值for(int i=1;i<=N;i++){for(int j=1;j<=c[i];j++){for(int k=M;k>=w[i];k--){dp[k]=Math.max(dp[k], dp[k-w[i]]+v[i]);}}}System.out.println(dp[M]);//最终输出容积为M的背包的最大价值即为题解}}

G - 最长上升子序列

        一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ..., aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).

        你的任务，就是对于给定的序列，求出最长上升子序列的长度。

Input

        输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

Output

        最长上升子序列的长度。

Sample

7
1 7 3 5 9 4 8

4

        题解：DP(动态规划)

import java.util.Scanner;public class Test07 {//最长上升子序列public static void main(String[] args) {Scanner cin=new Scanner(System.in);int N=cin.nextInt();int A[]=new int[N];for (int i=0;i<N;i++){A[i]=cin.nextInt();}int dp[]=new int[N];//dp[i]表示第i个数时当前的最长上升子序列的长度dp[0]=1;int maxans=1;for (int i=1;i<N;i++){dp[i]=1;for (int j=0;j<i;j++){if (A[i]>A[j]){//如果大于前面的某个数就去更新dp[i]dp[i]=Math.max(dp[i],dp[j]+1);}}maxans=Math.max(maxans,dp[i]);//每次求出dp[i]去更新最大值}System.out.println(maxans);//最终的最大长度即为题解}
}

H - 最长公共子序列Lcs

        给出两个字符串A B，求A与B的最长公共子序列（A,B的长度 <= 1000，子序列不要求是连续的）。

        比如两个串为：

        A：abcicba    B：abdkscab

        ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

Input

        第1行：字符串A 第2行：字符串B

Output

        输出最长的子序列，如果有多个，随意输出1个。

Sample

abcicba
abdkscab

abca

        题解: DP(动态规划),字符串

import java.util.Scanner;public class Test08 {//最长公共子序列Lcspublic static void main(String[] args) {/*最长公共子序列（longest common sequence）和最长公共子串（longest common substring）不一样。子序列：公共序列 可以不相邻公共子串：公共序列的字符必须连续。公共子数组： 数组索引必须连续*/Scanner cin = new Scanner(System.in);String A = cin.next();String B = cin.next();int al = A.length();int bl = B.length();int dp[][] = new int[al + 1][bl + 1];//定义一个dp数组，dp[i][j]表示A字符串的前i个字符构成的字符串与B字符串的前j个字符构成的字符串所共有的最大公共子序列的长度for (int i = 1; i <= al; i++) {for (int j = 1; j <= bl; j++) {if (A.charAt(i - 1) == B.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}//计算完dp数组后查找出最大子序列并输出StringBuffer sb=new StringBuffer();while (al>0&&bl>0){if (dp[al][bl]>Math.max(dp[al-1][bl],dp[al][bl-1])){//说明该位置的字符为最大子序列中的其中一个字符sb.insert(0,A.charAt(al-1));al--;bl--;}else {if (dp[al-1][bl]>dp[al][bl-1]){al--;}else {bl--;}}}System.out.println(sb);//最终输出该字符串即为题解}
}

I - 石子合并

        将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入格式

        输入第一行一个整数 n，表示有 n 堆石子。

        第二行 n 个整数，表示每堆石子的数量。

输出格式

        输出共两行：

        第一行为合并得分总和最小值，

        第二行为合并得分总和最大值。

样例

4
4 5 9 4

43
54

数据范围与提示

        对于 100% 的数据，有 1≤n≤200。

        题解 ：DP(动态规划)

import java.util.Scanner;public class Test09 {//石子合并(圆形)static int n;static int[] sum;static int[] num;static int[][] f;	// f[i][j]表示从第i堆合并到第j堆的分数public static void main(String[] args) {Scanner cin = new Scanner(System.in);n = cin.nextInt();num = new int[2*n+1];f = new int[2*n+1][2*n+1];	// f[i][j]表示从第i堆合并到第j堆的分数//由于是圆形的操场，则需要考虑循环数组，即创建一个2n大小的数组for(int i=1;i<=n;i++) {num[i] = cin.nextInt();}for(int i=n+1;i<=n*2;i++) {num[i] = num[i-n];}int min=999999,temp,max=0;for(int i=1;i<=n;i++) {temp=dpMin(i,n-1+i);if(min>temp) {min=temp;}}for(int i=1;i<=n;i++) {temp=dpMax(i,n-1+i);if(max<temp) {max=temp;}}System.out.println(min);System.out.println(max);}public static int dpMax(int strat,int end) {//求最大值for(int i=strat;i<=end;i++) {sum[i] = num[i]+sum[i-1];}for(int i=strat;i<=end;i++)for(int j=1;j<=end;j++)f[i][j]=0;for(int i=end-1;i>=strat;i--)for(int j=i+1;j<=end;j++)for(int k=i;k<=j-1;k++)f[i][j] = Math.max(f[i][j], f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);return f[strat][end];}public static int dpMin(int strat,int end) {//求最小值for(int i=strat;i<=end;i++) {sum[i] = num[i]+sum[i-1];}for(int i=strat;i<=end;i++)for(int j=1;j<=end;j++)f[i][j]=999999;for(int i=strat;i<=end;i++)f[i][i] = 0;for(int i=end-1;i>=strat;i--)for(int j=i+1;j<=end;j++)for(int k=i;k<=j-1;k++)f[i][j] = Math.min(f[i][j], f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);return f[strat][end];}
}

J - 循环数组最大子段和

        N个整数组成的循环序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续的子段和的最大值（循环序列是指n个数围成一个圈，因此需要考虑a[n-1],a[n],a[1],a[2]这样的序列）。当所给的整数均为负数时和为0。

        例如：-2,11,-4,13,-5,-2，和最大的子段为：11,-4,13。和为20。

Input

        第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N+1行：N个整数 (-10^9 <= S[i] <= 10^9)

Output

        输出循环数组的最大子段和。

Sample

6
-2
11
-4
13
-5
-2

20

        题解:DP(动态规划) 

import java.util.Scanner;public class Test10 {//循环数组最大子段和public static void main(String[] args) {
/*最大子段和正常数组中间的某一段和最大,这个可以通过普通的最大子段和问题求出。此数组(循环数组)首尾相接的某一段和最大,这种情况是由于数组中间某段和为负值，且绝对值很大导致的，那么我们只需要把中间的和为负值且绝对值最大的这一段序列求出，用总的和减去它就行了。即，先对原数组求最大子段和，得到max1，然后把数组中所有元素符号取反，再求最大子段和，得到max2，原数组的所有元素和为sum,那么最终答案就是 max(max1, max2+sum)*/Scanner cin=new Scanner(System.in);int N=cin.nextInt();int A[]=new int[N];int B[]=new int[N];long sum=0;for (int i=0;i<N;i++){A[i]=cin.nextInt();B[i]=-A[i];sum+=A[i];}long max1 = Integer.MIN_VALUE;long sum1 = 0;for (int i = 0; i < A.length; i++) {//求出原数组的最大子段和sum1 += A[i];if (sum1 > max1)max1 = sum1;if (sum1 < 0)sum1 = 0;}long max2=Integer.MIN_VALUE;long sum2=0;for (int i=0;i<B.length;i++){//求出所有都添加负号后的数组的最大子段和sum2+=B[i];if (sum2>max2)max2=sum2;if (sum2<0)sum2=0;}System.out.println(Math.max(max1,max2+sum));}
}

K - 没有上司的舞会

        某大学有N个职员，编号为1~N，校长的编号为1，他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

        现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数Ri，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

Input

        第一行一个整数N。(1<=N<=100000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司或者L是K的直接上司。

Output

        输出最大的快乐指数。

Sample

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

5

        题解:DP(动态规划),dfs,树

import java.util.*;
public class Test11{//没有上司的舞会public static List<Integer> son[];public static int w[],dp[][];  //0--No   1--Yespublic static void main(String[] args){Scanner cin=new Scanner(System.in);int n=cin.nextInt();son=new ArrayList[n+1];w=new int[n+1];dp=new int[n+1][2];for(int i=1;i<=n;i++)w[i]=cin.nextInt();int v[]=new int[n+1];for(int i=0;i<n-1;i++){int s=cin.nextInt();v[s]=1;int f=cin.nextInt();if(son[f]==null)son[f]=new ArrayList<Integer>();son[f].add(s);}int root=-1;for(int i=1;i<=n;i++){if(v[i]==0){root=i;break;}}dfs(root);System.out.println(Math.max(dp[root][1],dp[root][0]));}public static void dfs(int cur){if(son[cur]==null){dp[cur][0]=0;dp[cur][1]=w[cur];return;}for(int i=0;i<son[cur].size();i++){int curson=son[cur].get(i);dfs(curson);dp[cur][0]+=Math.max(dp[curson][0],dp[curson][1]);dp[cur][1]+=dp[curson][0];}dp[cur][1]+=w[cur];return;}
}

L - 滑雪

        Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

         1  2  3  4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

        一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

        输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

        输出最长区域的长度。

Sample

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

25

        题解:DP(动态规划),递归

import java.util.Scanner;public class Test12 {//滑雪static int R,C;static int arr[][],dp[][];public static void main(String[] args) {Scanner cin=new Scanner(System.in);R=cin.nextInt();C=cin.nextInt();arr=new int[R][C];for (int i=0;i<R;i++){for (int j=0;j<C;j++){arr[i][j]=cin.nextInt();}}dp=new int[R][C];int max=0;for (int i=0;i<R;i++){for (int j=0;j<C;j++){int temp=ski(i,j,Integer.MAX_VALUE);if (temp>max){//更新最大值max=temp;}}}System.out.println(max);}static int ski(int r,int c,int maxvalue){if (r>=R||r<0||c>=C||c<0||maxvalue<=arr[r][c]){//如果出现极端情况即出界则返回0return 0;}if (dp[r][c]>0){//若计算到达该点的滑雪长度则直接返回即可return dp[r][c];}//否则将其四个滑雪方向中找出其中的最大值+1dp[r][c] = max(ski(r-1, c, arr[r][c]), ski(r+1, c, arr[r][c]), ski(r, c-1, arr[r][c]), ski(r, c+1, arr[r][c])) + 1;return dp[r][c];}static int max(int ski, int ski1, int ski2, int ski3) {//四个方向的进行比较大小return Math.max(Math.max(ski,ski1),Math.max(ski2,ski3));}
}