网站建设const是什么意思,wordpress手机站,老年公寓网站模板,北京网络公司哪家最好蓝桥杯备赛系列
倒计时50天#xff01;
前缀和和差分
知识点
前缀和数组#xff1a; 假设原数组用a[i]表示#xff0c;前缀和数组用sum[i]表示#xff0c;那么sum[i]表示的是原数组前i项之和#xff0c;注意一般用前缀和数组时#xff0c;原数组a[i]的有效下标是从1开…蓝桥杯备赛系列
倒计时50天
前缀和和差分
知识点
前缀和数组 假设原数组用a[i]表示前缀和数组用sum[i]表示那么sum[i]表示的是原数组前i项之和注意一般用前缀和数组时原数组a[i]的有效下标是从1开始的。式子如下 s u m [ n ] ∑ i 1 n a [ i ] sum[n]\sum_{i1}^n a[i] sum[n]i1∑na[i] 差分数组 假设原数组用a[i]表示差分数组用d[i]表示那么d[i]表示的是a[i]和a[i-1]之差注意一般用差分数组时原数组a[i]的有效下标也是从1开始的。式子如下 d [ n ] a [ i ] − a [ i − 1 ] d[n]a[i]-a[i-1] d[n]a[i]−a[i−1] 接下来看一下前缀和和差分的模板题。
前缀和模板
题目描述
给定一个长度为 n n n的数组 a 1 , a 2 , . . . . a n . a_1,a_2,....a_n. a1,a2,....an.
接下来有 q q q次查询, 每次查询有两个参数 l , r l, r l,r.
对于每个询问, 请输出 a l a l 1 . . . a r . a_la_{l1}...a_r. alal1...ar.
输入描述
第一行包含两个整数 n n n和 q q q.
第二行包含n个整数, 表示 a 1 , a 2 , . . . . a n . a_1,a_2,....a_n. a1,a2,....an.
接下来q行,每行包含两个整数 l和r. 1 ≤ n , q ≤ 1 0 5 1≤n,q≤10^5 1≤n,q≤105 − 1 0 9 ≤ a [ i ] ≤ 1 0 9 −10^9≤a[i]≤10^9 −109≤a[i]≤109 1 ≤ l ≤ r ≤ n 1≤l≤r≤n 1≤l≤r≤n
输出描述
输出 q q q行,每行代表一次查询的结果.
样例输入
3 2
1 2 4
1 2
2 3样例输出
3
6题目分析
前缀和最经典的一个作用就是以O1的时间复杂度求区间和。
sum[l-1]a[1]a[2]a[3]…a[l-1]
sum[r]a[1]a[2]a[3]…a[l-1]a[l]…a[r]
sum[r]-sum[l-1]a[1]a[2]a[3]…a[l-1]a[l]…a[r]-(a[1]a[2]a[3]…a[l-1])
a[l]a[l1]…a[r]
所以区间[l,r]的和可以用sum[r]-sum[l-1]表示。
题目代码
import java.util.Scanner;
public class Main{
public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int q scanner.nextInt();int a[] new int[n1];long sum[] new long[n1];for(int i 1;i n;i) a[i] scanner.nextInt();for(int i 1;i n;i) sum[i] sum[i-1] a[i];while(q-- 0) {int l scanner.nextInt();int r scanner.nextInt();System.out.println(sum[r]-sum[l-1]);}
}
}二维前缀和模板
题目描述
给你一个 n 行 m 列的矩阵 A 下标从1开始。
接下来有 q 次查询每次查询输入 4 个参数 x 1 , y 1 , x 2 , y 2 x1 , y1 , x2 , y2 x1,y1,x2,y2
请输出以 ( x 1 , y 1 ) (x1, y1) (x1,y1)为左上角 ,$ (x2,y2)$ 为右下角的子矩阵的和
输入描述
第一行包含三个整数n,m,q.
接下来n行每行m个整数代表矩阵的元素
接下来q行每行4个整数 x 1 , y 1 , x 2 , y 2 x1, y1, x2, y2 x1,y1,x2,y2分别代表这次查询的参数 1 ≤ n , m ≤ 1000 1≤n,m≤1000 1≤n,m≤1000 1 ≤ q ≤ 1 0 5 1≤q≤10^5 1≤q≤105 − 1 0 9 ≤ a [ i ] [ j ] ≤ 1 0 9 −10^9≤a[i][j]≤10^9 −109≤a[i][j]≤109 1 ≤ x 1 ≤ x 2 ≤ n 1≤x1≤x2≤n 1≤x1≤x2≤n 1 ≤ y 1 ≤ y 2 ≤ m 1≤y1≤y2≤m 1≤y1≤y2≤m
输出描述
输出q行每行表示查询结果。
样例输入
3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4样例输出
8
25
32题目分析
首先要了解二维前缀和数组的定义 s u m [ i ] [ j ] sum[i][j] sum[i][j]表示的是对左上角行列分别为11右下角行列分别为ij的矩阵求和。 s u m [ 7 ] [ 7 ] sum[7][7] sum[7][7]如下图为红色圈起来的矩阵。注意这里矩阵的下标都是从1开始的。 我们通过图片分析如何求二维前缀和数组以及如何利用二维前缀和数组求矩阵和。 如何求二维前缀和数组。如图所示假设要求 s u m [ x 1 ] [ y 1 ] sum[x1][y1] sum[x1][y1]的值也就是图中大红色圈起来的部分我们可以将蓝色部分加上绿色部分后再加上x1,y1处本来的值也就是 s u m [ x 1 ] [ y 1 − 1 ] s u m [ x 1 − 1 ] [ y 1 ] a [ x 1 ] [ y 1 ] sum[x1][y1-1]sum[x1-1][y1]a[x1][y1] sum[x1][y1−1]sum[x1−1][y1]a[x1][y1]。但是这样会多加上一部分也就是蓝色和绿色重叠的部分他用 s u m [ x 1 − 1 ] [ y 1 − 1 ] sum[x1-1][y1-1] sum[x1−1][y1−1]表示需要减掉。综上 s u m [ x 1 ] [ y 1 ] s u m [ x 1 ] [ y 1 − 1 ] s u m [ x 1 − 1 ] [ y 1 ] a [ x 1 ] [ y 1 ] − s u m [ x 1 − 1 ] [ y 1 − 1 ] sum[x1][y1]sum[x1][y1-1]sum[x1-1][y1]a[x1][y1]-sum[x1-1][y1-1] sum[x1][y1]sum[x1][y1−1]sum[x1−1][y1]a[x1][y1]−sum[x1−1][y1−1]。 如何利用二维前缀和数组求矩阵和。如图所示假设要求左上角下标为x1,y1右下角下标为x2,y2的矩阵的值也就是图中蓝色的部分。可以用 s u m [ x 2 ] [ y 2 ] − s u m [ x 2 ] [ y 1 − 1 ] − s u m [ x 1 − 1 ] [ y 2 ] s u m [ x 1 − 1 ] [ y 1 − 1 ] sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]sum[x1-1][y1-1] sum[x2][y2]−sum[x2][y1−1]−sum[x1−1][y2]sum[x1−1][y1−1]表示也就是图中绿色部分减去图中橙色和紫色部分而紫色和橙色部分有重叠多减了要再加回来也就是图中棕色部分。
题目代码
代码细节数据的读入涉及到矩阵对于java而言数据量较大要使用快读。如果没有学过快读可以点击链接学习一下。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;public class Main {
public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[] strings br.readLine().split( );int n Integer.parseInt(strings[0]);int m Integer.parseInt(strings[1]);int q Integer.parseInt(strings[2]);long a[][] new long[n1][m1];long sum[][] new long[n1][m1];for(int i 1;i n;i) {strings br.readLine().split( );for(int j 1;j m;j) {a[i][j] Integer.parseInt(strings[j-1]);}}for(int i 1;i n;i) {for(int j 1;j m;j) {sum[i][j] sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]a[i][j];}}while(q-- 0) {strings br.readLine().split( );int x1 Integer.parseInt(strings[0]);int y1 Integer.parseInt(strings[1]);int x2 Integer.parseInt(strings[2]);int y2 Integer.parseInt(strings[3]);System.out.println(sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]sum[x1-1][y1-1]);}
}
}
差分模板题
题目描述
给你一个长度为n的正数数组 a 1 , a 2 , . . . . a n a_1,a_2,....a_n a1,a2,....an。
接下来对这个数组进行m次操作每个操作包含三个参数l,r,k代表将数组中 a l a l 1 . . . a r a_la_{l1}...a_r alal1...ar部分都加上k。
请输出操作后的数组。
输入描述
第一行包含两个整数n和m。 第二行包含n个整数表示 a 1 , a 2 , . . . . a n a_1,a_2,....a_n a1,a2,....an。 接下来是m行每行三个整数分别代表每次操作的参数l,r,k. 1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105 − 1 0 9 ≤ a [ i ] ≤ 1 0 9 −10^9≤a[i]≤10^9 −109≤a[i]≤109 1 ≤ l ≤ r ≤ n 1≤l≤r≤n 1≤l≤r≤n − 1 0 9 ≤ k ≤ 1 0 9 −10^9≤k≤10^9 −109≤k≤109
输出描述
输出1行表示m次操作后的 a 1 , a 2 , . . . . a n a_1,a_2,....a_n a1,a2,....an。
输入样例
3 2
1 2 3
1 2 4
3 3 -2输出样例
5 6 1题目分析
差分数组一般要结合前缀和使用使用方法如下
假设我有两个操作第一个操作是对下标为3一直到下标为10的数字都加上2第二个操作是对下标为4到下标为7的数字都加上3朴素的做法是遍历一遍要操作的数组区间然后执行操作就可以了两次操作过后原始数组累计要改变的值如下
a的下标1234567891011a要加上的值00255552220
这样做执行每次操作的时间复杂度是数组的长度。那么如何利用差分数组来做呢
对下标为3一直到下标为10的数字都加上2——d[3]2d[11]-2。
对下标为4到下标为7的数字都加上3——d[4]3d[8]-3。
然后求d数组的前缀和数组结果如下下标从1开始
sum的下标1234567891011sum的值00255552220
此时sum里面的值表示的是原始数组要变动的值将sum数组与原始数组相加即是操作后的结果可以发现是和表1一样的。而这样每次操作的时间复杂度是O1。
综上如果我要对区间[l,r]里的数加上k我只需要对差分数组进行操作即d[l]kd[r1]-k。
题目代码
import java.util.Scanner;public class Main {
public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();long[] a new long[n1];long[] s new long[n1];for (int i 1; i a.length; i) {a[i] scanner.nextInt();}while(m0) {m--;int l scanner.nextInt();int r scanner.nextInt();int k scanner.nextInt();s[l] k;if(r1n) {s[r1]-k;}}long sum[] new long[n1];for (int i 1; i s.length; i) {sum[i] sum[i-1]s[i];a[i] a[i]sum[i];System.out.print(a[i] );}
}
}二维差分模板题
题目描述
给你一个n行m列的矩阵下标从1开始。 接下来有q次操作每次操作输入5个参数x1, y1, x2, y2, k 表示把以(x1, y1)为左上角,(x2,y2)为右下角的子矩阵的每个元素都加上k 请输出操作后的矩阵。
输入描述
第一行包含三个整数n,m,q. 接下来n行每行m个整数代表矩阵的元素
接下来q行每行5个整数x1, y1, x2, y2, k分别代表这次操作的参数 1 ≤ n , m ≤ 1000 1≤n,m≤1000 1≤n,m≤1000 1 ≤ q ≤ 1 0 5 1≤q≤10^5 1≤q≤105 1 ≤ x 1 ≤ x 2 ≤ n 1≤x1≤x2≤n 1≤x1≤x2≤n 1 ≤ y 1 ≤ y 2 ≤ m 1≤y1≤y2≤m 1≤y1≤y2≤m − 1 0 9 ≤ 矩阵中的元素 ≤ 1 0 9 −10^9≤矩阵中的元素≤10^9 −109≤矩阵中的元素≤109
输出描述
输出n行每行m个数每个数用空格分开表示这个矩阵。
样例输入
2 3 4
1 2 3
4 5 6
1 1 2 2 3
1 2 2 3 -1
1 1 1 3 4
1 1 2 1 1样例输出
9 8 6
8 7 5题目分析
二维差分模板关键在于确定好在差分数组的哪些地方更改值。假设要更改的地方是从下标2,4到下标3,6的位置加1那么首先必然是让2,4的位置加1这样之后对差分数组求前缀和的结果如图所示 我们要更改的是绿色圈起来的部分但是之外的部分也更改了我需要把这部分更改变回来我想让2,6之后的从2,7开始都是0既然2,4加了1那么对应的2,7这一部分之后我要减掉1来抵消前面的加1。同样44也要减1来抵消2,4的加1。这样就可以了吗这样相当于有两个位置减1一个位置加1一看也不对呀对于4,7这个位置应该是没有变化的但是它的前缀和所包含的格子里2,4加了12,7减了144也减了1相当于4,7这个位置减了1我们要把这个减1抵消所以要在4,7这里加1。
综上对x1,y2到x2,y2的格子都进行加k操作只需要x1,y1kx1,y21-kx21,y1-kx21,y21k。
然后对差分数组求二维前缀和之后把结果累加到原始数组上就可以了。
题目代码
import java.util.Scanner;
public class Main{public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();int m scanner.nextInt();int q scanner.nextInt();long[][] a new long[n 1][m 1];long[][] b new long[n 1][m 1];long[][] sum new long[n 1][m 1];for (int i 1; i n; i) {for (int j 1; j m; j) {a[i][j] scanner.nextLong();}}while ((q--) ! 0) {int x1 scanner.nextInt();int y1 scanner.nextInt();int x2 scanner.nextInt();int y2 scanner.nextInt();int k scanner.nextInt();b[x1][y1] k;if (y2 1 m) {b[x1][y2 1] - k;}if (x2 1 n) {b[x2 1][y1] - k;}if (x2 1 n y2 1 m) {b[x2 1][y2 1] k;}}for (int i 1; i n; i) {for (int j 1; j m; j) {sum[i][j] sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]b[i][j];a[i][j] sum[i][j];System.out.print(a[i][j] );}System.out.println();}}
}abb
题目描述
leafee 最近爱上了 abb 型语句比如“叠词词”、“恶心心”
leafee 拿到了一个只含有小写字母的字符串她想知道有多少个 “abb” 型的子序列 定义 abb 型字符串满足以下条件
字符串长度为 3 。字符串后两位相同。字符串前两位不同。
输入描述
第一行一个正整数 n
第二行一个长度为 n 的字符串只包含小写字母 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105
输出描述
“abb” 型的子序列个数。
样例输入
6
abcbcc样例输出
8共有1个abb3个acc4个bcc
题目分析
在abcbcc中acc的个数为3他是哪3个呢可以看下图a的后面有3个c在这3个c里面任选两个c可以和a组成一个叠词那么组合的种类为 C 3 2 C_3^2 C32也就是 3 ∗ 2 / 2 3 3*2/23 3∗2/23种。假设字母a后面有num个相同的字母那么它能够贡献的叠词个数为 C n u m 2 C_{num}^2 Cnum2也就是 n u m ∗ ( n u m − 1 ) / 2 num*(num-1)/2 num∗(num−1)/2个。因此我们需要求出每个字母后面出现的其它相同字母的个数。 对于上图字符串因为求的是后面的字符出现的次数所以我们倒序遍历去求。位置6c出现了一次用 n u m [ 6 ] [ c ] 1 num[6][c]1 num[6][c]1表示位置5c出现了1次用 n u m [ 5 ] [ c ] 1 num[5][c]1 num[5][c]1表示位置3c出现了一次用 n u m [ 3 ] [ c ] 1 num[3][c]1 num[3][c]1表示其余位置 n u m [ 1 , 2 , 4 ] [ c ] 1 num[1,2,4][c]1 num[1,2,4][c]1都是0。那么求位置4后面包括位置4在内c出现的次数应该是位置6的c累加上位置5的c即 n u m [ 5 ] [ c ] n u m [ 6 ] [ c ] num[5][c]num[6][c] num[5][c]num[6][c]求位置1后面c出现的次数应该是 n u m [ 2 ] [ c ] n u m [ 3 ] [ c ] n u m [ 4 ] [ c ] n u m [ 5 ] [ c ] n u m [ 6 ] [ c ] 0 1 0 1 1 3 num[2][c]num[3][c]num[4][c]num[5][c]num[6][c]010113 num[2][c]num[3][c]num[4][c]num[5][c]num[6][c]010113。这里其实就是前缀和数组或者说是后缀和数组因为求的是后面的值累加的结果。
综上我们用 n u m s [ i ] [ c ] nums[i][c] nums[i][c]表示下标为i的位置的右边字符c出现的总次数。这里的数组就是后缀和数组。即 n u m s [ i ] [ c ] n u m [ i 1 ] [ c ] n u m [ i 2 ] [ c ] . . . n u m [ n ] [ c ] nums[i][c]num[i1][c]num[i2][c]...num[n][c] nums[i][c]num[i1][c]num[i2][c]...num[n][c]。
那么 n u m s [ i ] [ c ] n u m s [ i 1 ] [ c ] n u m [ i ] [ c ] nums[i][c]nums[i1][c]num[i][c] nums[i][c]nums[i1][c]num[i][c]。
题目代码
import java.util.Scanner;
public class abb {
public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();char[] s ( scanner.next()).toCharArray();int pre[][] new int[n2][26];for(int i n;i 1;i--) {for(int j 0;j 26;j) {//求下标为i的位置包括下标i在内26个字母中每个字母出现的次数。这里要用到前缀和pre[i][j] pre[i1][j];}pre[i][s[i]-a];//这里就是加上位置i的字母}long sum 0;for(int i 1;i n;i) {for(int j 0;j 26;j) {//注意这里要有j!s[i]-a的判断因为aaa是不合法的//同样也要有pre[i][j]2的判断因为后面至少要有两个才能组合出acc//pre[i1][j]是i1因为pre[i][j]包含了位置i的字母但是我们求的是i后面的字母//但其实用pre[i][j]也没有问题因为这里的字母j肯定和位置i的字母不一样那么必然不会对pre[i][j]数组产生作用因为这里的num[i][j]0if(pre[i][j]2j!s[i]-a) sum (pre[i1][j]-1)*pre[i
1][j]/2;}}System.out.println(sum);
}
}鼠鼠我鸭
题目描述
在一个叫做酱西功爷枝叶鸡树学院的地方有n只小动物要么是鼠鼠要么是鸭鸭从1到n编号每只小动物有个体重 a i a_i ai。
在这个学校里存在一种神奇的魔法可以将编号位于某个区间 [ l , r ] [l,r] [l,r]内的所有鼠鼠都变为鸭鸭鸭鸭都变为鼠鼠魔法并不会改变体重。
现在你可以施放这个魔法至多1次。也可以不施放
问最终鸭鸭的总重量最多是多少
输入格式
第一行一个整数T表示样例个数。 ( 1 ≤ T ≤ 10 ) (1≤T≤10) (1≤T≤10)
对于每个样例
第一行一个整数n表示小动物的个数。( 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105)
第二行 n n n个整数表示第 i i i个小动物的类型。0表示鼠鼠1表示鸭鸭。
第三行 n n n个整数表示第 i i i个小动物的体重 a i a_i ai。( 1 ≤ a i ≤ 1 0 9 1≤a_i≤10^9 1≤ai≤109)
输出格式
对于每个样例一行一个整数表示答案。
样例输入
2
3
0 0 0
1 2 3
4
0 1 0 0
2 5 6 5样例输出
6
16题目分析
假设原本所有鸭鸭的重量是sum操作后形成的偏移是fix即经过至多1次操作后鸭鸭的总重量是sumfix这里的fix最小是0因为如果操作后的fix是负数会使得鸭鸭的总重量减少倒不如不操作直接是sum就可以了。
来看这个fix应该怎么求。以样例的第二组数据为例如果操作区间是[0,4]那么每个位置对应的偏移量分别为2-565。总的偏移量为2-5658。如果操作区间是[1,2]总的偏移量为-561。其实要求某个区间的偏移量就是数组[2-565]对应区间的区间和。这里的[2-565]也叫做偏移量数组因为对于位置i的值而言如果他是鸭鸭一次操作后就变为了鼠鼠那么之前累加上的他的重量应该减去所以偏移量就是负的该位置的重量也就是-a[i]如果他是鼠鼠一次操作后就变为了鸭鸭他的重量应该累加上所以偏移量就是该位置的重量也就是a[i]。所以我们可以求一下偏移量数组的前缀和然后利用前缀和求最大的偏移量区间和也就是一开始说的fix累加到原始的重量和sum里面就好。
假设偏移量的前缀和数组是pre[i]那么偏移量的区间和[l,r]就用pre[r]-pre[l-1]如果我们遍历l和r的话双层嵌套for循环会超时所以这里应该采用类似双指针的做法假设固定了r要想pre[r]-pre[l-1]最大需要pre[l-1]是区间[1,l-1]里面最小的那个数用mi表示关键代码如下
fix0;mi0;
for(int i1;in;i) {fixmax(fix,s[i]-mi);//i固定时mi是下标比i小的数中的最小值mimin(mi,s[i]);}fix最小是0所以初始化为0。这里的mi最小值也为0mi为0时表示的是区间[1,i]的区间和如果mi不为负数说明s[i]-mi会变小即比s[i]本身小倒不如直接用s[i]s[i]表示的就是前i项之和也是区间和。
题目代码
#include bits/stdc.h
using namespace std;
typedef long long ll;const int N1e510;
ll g[N],w[N],s[N],p[N];
ll sum,fix,mi;int main(){int t;cint;while(t--){int n;cinn;for(int i1;in;i)cing[i];for(int i1;in;i)cinw[i];for(int i1;in;i){s[i]s[i-1](g[i] 1 ? -1 : 1)*w[i]; //计算出施加魔法后的偏移值鸭子重量如果原来是1鸭子就要减去原来是0鼠就加上}sum0;for(int i1;in;i) {sumw[i]*g[i];}fix0,mi0;for(int i1;in;i){fixmax(fix,s[i]-mi);mimin(mi,s[i]);}coutsumfix\n;}return 0;
}
代码有一个易错点因为变量都是全局变量所以sumfixe在每一组测试样例中都要重置为初始值。
import java.util.Scanner;
public class Main{static int N(int) (1e510);static long[] gnew long[N],wnew long[N],snew long[N],pnew long[N];static long sum,fix,mi;
public static void main(String[] args) {int t;Scanner scanner new Scanner(System.in);t scanner.nextInt();while(t-- 0){int n;n scanner.nextInt();for(int i1;in;i)g[i]scanner.nextLong();for(int i1;in;i)w[i]scanner.nextLong();for(int i1;in;i){s[i]s[i-1](g[i] 1 ? -1 : 1)*w[i]; //计算出施加魔法后的偏移值鸭子重量如果原来是1鸭子就要减去原来是0鼠就加上}sum0;for(int i1;in;i) {sumw[i]*g[i];}fix0;mi0;for(int i1;in;i) //从第一个遍历到最后计算出最大最小值{fixMath.max(fix,s[i]-mi);miMath.min(mi,s[i]);}System.out.println(sumfix);}}
}前缀和的拓展——压缩矩阵
最大子段和
题目描述
给出一个长度为 n n n 的序列 a a a选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数表示序列的长度 n n n。
第二行有 n n n 个整数第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。
输出格式
输出一行一个整数表示答案。
样例输入
7
2 -4 3 -1 2 -4 3样例输出
4选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}其和为 4 4 4。
数据规模
对于 40 % 40\% 40% 的数据保证 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。对于 100 % 100\% 100% 的数据保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105 − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 −104≤ai≤104。
题目分析
提供一下类似动态规划的解法而这个动态规划dp数组的定义类似最长上升子序列里面dp数组的定义。
第一阶段定义dp数组
直接定义dp数组。dp[i]表示以第i个字母结尾的最大字段和。
第二阶段推导状态转移方程
对于dp[i]我可以从两个地方转移过来即以a[i-1]结尾的最大子段和加上a[i]和a[i]自己那么从这两个转移状态里面选一个最大的就可以了状态转移方程是下面的式子。 d p [ i ] m a x ( d p [ i − 1 ] a [ i ] , a [ i ] ) dp[i]max(dp[i-1]a[i],a[i]) dp[i]max(dp[i−1]a[i],a[i])
第三阶段写代码
1dp数组初始化。这里求的是最大值一般初始状态是为0但是这里可能会出现负数的情况要初始化为较小值吗不需要我们可以看一下 d p [ 1 ] m a x ( d p [ 0 ] a [ 1 ] , a [ 1 ] ) dp[1]max(dp[0]a[1],a[1]) dp[1]max(dp[0]a[1],a[1])这里的dp[0]0是对的因为对于前0个数字它的和就是0。每次dp[i]都会可能的值被更新而dp[i1]只用到了dp[i]。所以不用初始化。写的有点啰嗦了。
2递推dp数组。这里只需要遍历一次a数组就行了。
3答案。min(dp[i])。
题目代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {Scanner scannernew Scanner(System.in);int n scanner.nextInt();int a[] new int[n1];int dp[] new int[n1];int ans Integer.MIN_VALUE;for(int i 1;i n;i) {a[i] scanner.nextInt();dp[i] Math.max(dp[i-1]a[i], a[i]);ans Math.max(dp[i], ans);}System.out.println(ans);
}
}最大加权矩形
题目描述
为了更好的备战 NOIP2013电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为我们不光需要机房我们还需要运动于是就决定找校长申请一块电脑组的课余运动场地听说她们都是电脑组的高手校长没有马上答应他们而是先给她们出了一道数学题并且告诉她们你们能获得的运动场地的面积就是你们能找到的这个最大的数字。
校长先给他们一个 n × n n\times n n×n 矩阵。要求矩阵中最大加权矩形即矩阵的每一个元素都有一权值权值定义在整数集上。从中找一矩形矩形大小无限制是其中包含的所有元素的和最大 。矩阵的每个元素属于 [ − 127 , 127 ] [-127,127] [−127,127] ,例如 0 –2 –7 0 9 2 –6 2
-4 1 –4 1
-1 8 0 –2在左下角
9 2
-4 1
-1 8和为 15 15 15。
几个女孩子有点犯难了于是就找到了电脑组精打细算的 HZHTZY 小朋友帮忙计算但是遗憾的是他们的答案都不一样涉及土地的事情我们可不能含糊你能帮忙计算出校长所给的矩形中加权和最大的矩形吗
输入格式
第一行 n n n接下来是 n n n 行 n n n 列的矩阵。
输出格式
最大矩形子矩阵的和。
样例输入
4
0 -2 -7 09 2 -6 2
-4 1 -4 1
-1 8 0 -2样例输出
15数据规模 1 ≤ n ≤ 120 1 \leq n\le 120 1≤n≤120
题目分析
这道题是最大子段和的二维形式。可尝试把它压缩成一维。我们利用前缀和对矩阵进行行压缩。行压缩的结果是 a [ i ] [ j ] a[i][j] a[i][j]里面存的是前i行第j列的和其实就是相对于第j列的前缀和。假设 a [ i ] [ j ] a[i][j] a[i][j]初始值是矩阵的值那么类比于 s u m [ i ] s u m [ i − 1 ] a [ i ] sum[i]sum[i-1]a[i] sum[i]sum[i−1]a[i]的前缀和求解方法可以利用下式求前缀和 a [ i ] [ j ] a [ i − 1 ] [ j ] a[i][j]a[i-1][j] a[i][j]a[i−1][j] 求完前缀和后如果我要求第j列第l行到第r行的和用 a [ r ] [ j ] − a [ l − 1 ] [ j ] a[r][j]-a[l-1][j] a[r][j]−a[l−1][j]表示。如果我要求以i行结尾的矩阵的最大值那么应该怎么求如下图所示 原本我求第j列某几行的和我需要依次相加但是压缩后我只需要用一个式子一下子就可以表示出来第j列某几行的和现在相当于把矩阵压缩成了一维的形式我只需要移动j就可以了。定义两个数组f[j]和dp[j]dp[j]的含义和最大子段和的含义一样在行固定的情况下以第j列结尾的最大矩阵和那么它的转移也和最大子段和一样f[j]就表示在行固定的情况下第j列的矩阵和它相当于最大子段和里面的a[i]。
对应的关键代码如下
for(int i 1;i n;i) {for(int k 1; k i;k) {int f[] new int[n1];int dp[] new int[n1];for(int j 1;j n;j) {f[j] a[i][j]-a[i-k][j];dp[j] Math.max(dp[j-1]f[j], f[j]);ans Math.max(dp[j], ans);}}}要想固定行最低行和最高行都要固定所以两层for循环是不可少的固定了行之后再遍历列就可以了。
题目代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;public class Main {
public static void main(String[] args) throws IOException {BufferedReader br new BufferedReader(new InputStreamReader(System.in));Scanner scanner new Scanner(System.in);int n scanner.nextInt();int a[][] new int[n1][n1];for(int i 1;i n;i){int id 1;for(int j 1;j n;j) {a[i][j] scanner.nextInt();a[i][j] a[i-1][j];//利用前缀和进行矩阵的行压缩}}long ans 0;for(int i 1;i n;i) {for(int k 1; k i;k) {int f[] new int[n1];int dp[] new int[n1];for(int j 1;j n;j) {f[j] a[i][j]-a[i-k][j];dp[j] Math.max(dp[j-1]f[j], f[j]);ans Math.max(dp[j], ans);}}}System.out.println(ans);
}
}如果题目分析有错误或者没有表达清楚的地方欢迎在评论区里指出
