糖果盒(最大权值子矩阵)解题报告

最大子矩阵和问题问题描述：给定一个m 行n 列的整数矩阵a ，试求矩阵a 的一个子矩阵，使其各元素之和为最大。

分析：用2 维数组a [1 : m ][1 : n ]表示给定的m 行n 列的整数矩阵。

子数组a[i 1 : i 2][j 1 : j 2]表示左上角和右下角行列坐标分别为(i 1, j 1)和(i 2, j 2)的子矩阵，其各元素之和记为：∑∑===2121]][[),,,(2121j j j i i i j i a j j i i s （1）最大子矩阵和问题的最优解即为：（2）（3） 如果令：那么 （4）式（4）就是我们熟悉的最大子序列和的问题。

根据以上分析我们可得到最大子矩阵和问题的算法： Max_Sub_Matrix (m, n, a) //m 为行数，n 为列数，a 为二维矩阵1 sum ← 02 b[n]3for i ←1 to m 4for t ←1 to n 5do b[t] = 0 //初始化数组b 6 for j ←i to m7 do for k ←1 to n8 b[k] ← b[k] + a[j][k]9 max ←Max_Sub_List(n, b) //函数返回n 个数的序列b 的最大子序列的和 10 if max > sum then sum = max11 return sum下面我们就通过来同学上课提出的一些特殊情况来检验算法的正确性。

)2,1,2,1(211211j j i i s Max nj j mi i ≤≤≤≤≤≤)]][[()]][[()2,1,2,1(21212112112121211*********∑∑∑∑====≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤≤==j j j i i i j j j i i i j i a Max Max j i a Max Max j j i i s Max n j j j m i i i n j j j m i i i n j j mi i ∑=≤≤≤=2121]][[][1j j j n j j j i a Max j t ∑=≤≤≤=≤≤≤≤≤≤2121211211][)2,1,2,1(1j j j n j j j t Max j j i i s Max nj j m i i矩阵a 的行m=3当i = 1时，初始化数组b ，使得8行可得数组b 将首先存储矩阵的第一行的各值，即b 为：由最大子序列和的函数Max_Sub_List 返回该序列的最大子序列的和值为max=30；当j = 2时，k 从1递增到n ，由算法的第8行可得数组b 将矩阵a 第二行的值分别加到原有各值上，可得数组b 为同理，由函数Max_Sub_List 返回该序列的最大子序列的和值为max=125。

最长公共子序列的最优值和最优解
最长公共子序列问题是求解两个序列中最长的相同子序列的问题。

假设两个序列分别为A和B，其长度分别为m和n。

则最长公共子序列的最优值可以用一个m*n的矩阵c来表示。

矩阵c的第i行第j列表示序列A的前i个元素与序列B的前j个元素的最长公共子序列的长度。

为了求解矩阵c，可以采用动态规划的方法。

具体实现方法如下：
1. 定义一个m*n的矩阵c和一个长度为m的数组b。

2. 通过循环，初始化矩阵c和数组b，使其元素值均为0。

3. 使用两个循环，遍历序列A和B的每个元素，如果元素相同，则将矩阵c的对应位置赋值为左上角元素值加1，并将数组b的对应位置赋值为1；否则将矩阵c的对应位置赋值为左侧和上方元素的较大值。

4. 遍历完序列A和B后，矩阵c的最后一个元素即为两个序列的最长公共子序列的长度。

5. 通过倒序遍历数组b，将序列A中对应元素添加到结果序列中，直至遍历完所有元素。

最终，得到的结果序列即为最长公共子序列的最优解。

在实际应用中，最长公共子序列问题有着广泛的应用，如字符串匹配、生物信息学和版本控制等方面。

JOISC2019题解LOJ3030「JOISC 2019 Day1」考试显然的三维数点。

LOJ3031「JOISC 2019 Day1」聚会这题很 emmmm 啊……⼀个其实⽐较显然的随机做法：随机两个点x,y，对于每个点z询问 (x,y,z) ，即可知道它是在链上还是在链上的某个点的⼦树⾥。

对于链上的点可以⽤ stable_sort 找出之间的顺序，⼦树内的递归处理。

不知道期望多少次，但是过了。

还有⼀个做法，但是没有看懂……LOJ3032「JOISC 2019 Day1」馕反正我想不到 /kk对于每个⼈求出对于他来说把 naan n等分的分割点，然后每次找到还没有确定位置的⼈⾥⾯第i个分割点最⼩的⼈，把他放在这⾥。

正确性很显然。

LOJ3033「JOISC 2019 Day2」两个天线这题不会，脑⼦没了……由于是求绝对值的最⼤值，所以不妨把贡献设为i<j,H i−H j，然后再把H取相反数即可。

离线，从左往右枚举r，也就相当于是枚举j。

对于⼀个i，只有j∈[A i+i,B i+i] 的时候才是可⽤的。

⽽对于j，相当于是对 [j−B j,j−A j] ⾥⾯可⽤的i和H i−H j取max。

然后可以线段树维护：线段树的⼀个节点维护最⼤值、区间可⽤的max H i、区间能贡献的最⼩的H j。

LOJ3034「JOISC 2019 Day2」两道料理竟然切了，那就不写题解了。

LOJ3035「JOISC 2019 Day2」你LOJ⼜咕了考虑两边⼀起做 dijkstra ，那么每次需要知道两边分别扩展出的最近点是谁，以及距离是多少，然后选择较⼩的那⼀边扩展。

那么需要转移的 bit 是kn，其中k不是很⼩。

但不管怎样，数量级已经对了，所以尝试把k压⼩。

⼀个优化是：先互相传最⼩距离，然后距离更⼩的那⼀边把点的编号传过去。

但是由于距离⽐较⼤，还是卡不进去。

发现其实可以传d′=d−lastd，即⽐上⼀次多了多少。

求最大子矩阵的两种思路长沙市雅礼中学贺一骏编者：求最大子矩阵问题是很常见的一类问题，具有很强的代表性，通过这个问题，可以派生出更加复杂的问题，也可以学到很多常用的问题处理手段。

问题描述一个被分为 n*m个格子的月饼盒，第 i 行第 j 列位置的格子里面有 a [ i , j ]个月饼。

本来CCC老师打算送这盒月饼给某人的，但是就在要送出月饼盒的前一天晚上，一只极其可恶的老鼠夜袭月饼盒，有部分格子被洗劫并且穿了洞。

CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒，新的月饼盒不能有洞，并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。

任务：请帮CCC老师设计一个程序，计算一下新月饼盒最多能够保留多少月饼。

输入文件的第一行有两个整数 n、m。

第 i + 1 行的第 j 个数表示 a [ i , j ]，如果这个数为 0 ，则表示这个位置的格子被洗劫过。

其中：1 ≤ n，m ≤ 300，0 ≤a [ i , j ]≤ 255输出在文件中写入最大月饼数。

样例Sample Input3 41 2 3 45 06 310 3 4 0Sample Output17分析该问题实际上是求在给定平面区域中找出一个最大的子矩形，要求该矩形不能包含某些限定的格子。

方法一：我们初次见到这个问题，可能最直接的想法就是枚举。

即枚举每个矩阵的左上角坐标（x1,y1）和右下角坐标(x2,y2)，然后统计这个矩阵是否满足题设条件。

我们可以先预处理从左上角（1,1）出发到任意一点（i,j）的月饼数目area(i,j)，预处理的时间复杂度为O(mn),程序如下：For i:=1 to n doFor j:=1 to m doArea[I,j]:=area[i-1,j]+area[i,j-1]-area[i-1,j-1]+mooncake[i,j];其边界条件为area[0,i]=0,area[i,0]=0Mooncake[i,j]表示(i,j)这个点的上月饼数目，如果(i,j)这个点被破坏，则设mooncake[i,j]=-30000000，那么有area[i,j]<0。

试题名称关键字矩阵翻硬币兰顿蚂蚁分糖果小朋友排队波动数列斐波那契地宫取宝蚂蚁感冒最大子阵城市建设邮局数字游戏国王的烦恼回文数字公式求值组合数学九宫重排搜索车轮轴迹计算几何约数倍数选卡片博弈论农场阳光计算几何格子刷油漆动态规划高僧斗法博弈论网络寻路构图危险系数割点道路和航路最短路金属采集树形动态规划矩阵翻转枚举贪心两条直线排序3000米排名预测递归搜索大数加法高精度加法三角形面积a基础顺序校门外的树数组彩票一维数组笨小猴NOIP2008提高组选择排序色盲的民主插入排序找素数素数筛选扫雷促销购物g背包凶手去注释字符流处理、循环逻辑高精度加法b字符串数组6-9删除数组中的0元素数组操作3-2字符串输入输出函数函数进制转换基本运算数学知识c++_ch06_02c++_ch03_02c++_ch02_03c++_ch02_02Quadratic Equation基本运算数学知识温度转换基本运算数学知识征税程序基本运算数学知识分数统计猜测排名欧拉函数不同单词个数统计数组运算字符操作打水问题单词个数统计字符操作断案逻辑判断栅格打印问题循环语句复数求和字符串比较任意年月日历输出求最大公约数素数判断输出日历输出九九乘法表输出正反三角形利息计算格式化数据输出算术运算图形输出寻找三位数填充蛋糕简单计算数的运算语言指针选最大数语言指针时间转换算法普通计算最长单词算法枚举统计平均成绩语言二维数组GDP计算语言循环简单计算器语言switch语句计算整数因子数组输出数组循环一元一次方程输入输出判断回文循环字符串冒泡法排序排序数组质因数循环数论企业奖金发放循环逻辑传染病控制NOIP2003 提高组搜索阮小二买彩票格子位置乘法运算利息计算输入函数，输出函数，基本算数运算夺宝奇兵矩阵乘方多项式输出交换Easy项链实数相加统计单词数和最大子序列卡勒沃夫之弱水路三千(提高型)最小乘积(提高型)计算时间Torry的困惑(提高型)立方体截断问题递归倒置字符数组冒泡排序计数组合子集选取组合邮票面值设计搜索数列排序数组排序十六进制转八进制进制转换字符循环十六进制转十进制进制转换字符处理判断十进制转十六进制循环整除求余判断特殊回文数回文数循环条件语句回文数循环判断回文数特殊的数字循环判断数位杨辉三角形基础练习二维数组查找整数循环判断数列特征循环最大值最小值累加字母图形循环字符串01字串循环闰年判断条件判断阶乘计算高精度高精度加法数组高精度Huffuman树贪心Huffuman2n皇后问题八皇后问题搜索报时助手字符串条件判断回形取数二维数组循环龟兔赛跑预测数组模拟芯片测试算法基础统计二维数组FJ的字符串字符串递归Sine之舞字符串递归递推数的读法判断函数完美的代价贪心算法矩形面积交判断线段交矩阵乘法二维数组循环矩阵分解质因数质数分解循环字符串对比字符串大小写时间转换取余数字字符混合输出。

1.物品选取【题目大意】容量为m的背包挑选n样物品使得总价值最大。

【考察算法】DP+模型转换虽然有三类物品，其实相互不会影响，可以独立做。

【方法一】仅仅考虑B，C两类物品的情况，使用一般背包做法。

做B类时要用队列或二进制等优化。

时间复杂度：O(NM),期望的得分50。

【方法二】对于只有B，C两类物品的情况，是一个常见的背包问题，对于只有A的情况，也是一个简单的资源分配模型，为了能够同时考虑三种物品，我们可以考虑转换模型，将背包物品转换为资源分配物品，那么对于B类有限物品，转换之后价值函数为：对于C类无限物品，价值函数为：然后使用常见的资源分配模型求解。

, 时间复杂度：O(NM^2),期望的得分70。

【方法3】我们也可以将资源分配转换成背包问题，对于B，C两类物品仍然是按照普通方法处理，对于A类物品也只需要枚举分配给物品的空间。

时间复杂度：O(NM) – O(N*M^2),期望的得分100。

2.蛇形数阵【思路点拨】3.正则表达式【题目大意】求1到N的最短路。

【题目考点】SCC缩点单源最短路【算法一】题意比较清晰，简而言之就是处于同一个SCC的顶点之间的传输可以看作是0时间，然后求1到N的最短路。

那么我们只需要Tarjan或者Kosaraju之后在新图中然后使用Floyd或者朴素Dijkstra求最短路。

时间复杂度：O(N^2)/O(N^3),期望得分50。

【算法二】在缩点之后，使用Dijkstra+Heap或者SPFA算法求最短路。

时间复杂度：O(kE)/O((V+E)logV),期望得分75。

【方法三】注意点的范围可能很大，无论是Tarjan还是Kosaraju都需要手工栈。

另外，由于边数很大，所以SPFA（O(kE)）会T掉3个点，所以需要用稳定的Dijkstra+堆优化（二叉堆即可）。

最后，C/C++需要读入优化才能AC。

时间复杂度：O(kE)/O((V+E)logV)，期望得分100。

共现矩阵解题报告ASSIGNMENT #2: WORD CO-OCCURRENCE MATRIX00948181 单子非1.共现矩阵问题统计文档中每两个词出现在同一个句子中的次数，统计共现矩阵对语义分析、数据挖掘都有重要意义。

本报告中，作者使用Hadoop编程，计算了莎士比亚文献集的共现矩阵。

作者采用了Stripe 的方法对数据传输格式进行了优化，将数据传输量减小了一半；并采用In-Map Combing策略和定制Combiner类，大幅减小了数据的规模。

Map的输出value格式采用了hadoop的Text类，以字符串方式传输并进行解析，方法简便。

最后，作者对得到的共现矩阵数据进行了解析，发现绝大多数词对的共现次数小于等于5，共现次数最高的单词大多是英语常用高频词；通过对非常用高频词的解析，还发现了一些有趣的现象，如：这些文献中大量使用古英语人称代词和语体，以及文献的主题多为王室相关。

2.共现矩阵问题的定义如下：在文档集合中，任意两个单词共同出现在同一句子中的次数构成一个矩阵，我们要编程求这个矩阵。

考虑到问题的大规模数据量和可扩展性，我们用hadoop 编程，使用MapReduce算法求解。

Hadoop编程中，用户可定制的部分有Mapper、Reducer、Combiner和Partition四部分。

我们这里主要关注Mapper、Reducer和Combiner的编写。

最朴素的算法是基于pair的算法。

3.3.1.PAIR方法下面简单介绍朴素的Pair方法。

Mapper：map方法处理每个句子，切词之后二重循环遍历句中每个单词a和b，将< <a, b>, 1>作为Mapper的输出发送。

输出格式中，key为二元组<a, b>，value为整数，代表出现频率。

Reducer：reduce方法收集到的数据中，key为<a, b>，代表统计的两个单词，确定了共现矩阵中的一个元素；value为list<int>，将其元素累加后，可以直接得到两个词的共现次数x。

【动态规划进阶】糖果盒Time Limit:10000MS Memory Limit:65536KTotal Submit:72 Accepted:14Description一个被分为n*m个格子的糖果盒，第i行第j列位置的格子里面有a[i,j]颗糖。

本来tenshi打算送这盒糖果给某plmm的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。

tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且tenshi希望保留在新糖果盒内的糖的总数尽量多。

任务：请帮tenshi设计一个程序计算一下新糖果盒最多能够保留多少糖果。

Input从文件candybox.in读入数据。

第一行有两个整数n、m。

第i + 1 行的第j 个数表示a[i,j]，如果这个数为0，则表示这个位置的格子被洗劫过。

其中：1 ≤ n，m ≤ 4000 ≤ a [ i ][ j ]≤ 255Output输出最大糖果数到candybox.out。

Sample Input3 41 2 3 45 06 310 3 4 0Sample Output17Hint注：1 0 3 4这个矩形的糖果数最大Source∙var∙ i,j,k,n,m,xx,yy,max,t,max1:longint;∙ x,y:longint;∙ a,b,c,d:array[0..400,0..400] of longint;∙ data:array[0..400,0..400,1..2] of longint;{1,-,2,|}∙begin∙ readln(n,m);∙ for i:=1 to n do∙ for j:=1 to m do read(a[i,j]);∙ for i:=1 to n do∙ for j:=1 to m do {-----}∙ if a[i,j]=0 then b[i,j]:=0∙ else begin∙ b[i,j]:=b[i,j-1]+a[i,j];∙ data[i,j,1]:=data[i,j-1,1]+1;∙ end;∙ for i:=1 to m do∙ for j:=1 to n do {|||||}∙ if a[j,i]=0 then c[j,i]:=0∙ else begin∙ c[j,i]:=c[j-1,i]+a[j,i];∙ data[j,i,2]:=data[j-1,i,2]+1;∙ end;∙ max:=0;∙ for i:=1 to n do∙ for j:=1 to m do if a[i,j]<>0 then begin∙ d[i,j]:=a[i,j];∙ x:=data[i,j-1,1]; y:=data[i-1,j,2];∙ if data[i-1,j-1,1]<x then x:=data[i-1,j-1,1];∙ if data[i-1,j-1,2]<y then y:=data[i-1,j-1,2];∙ max1:=b[i,j];∙ if max1<c[i,j] then max1:=c[i,j];∙ if x*y<>0 then begin∙ xx:=x; yy:=y;∙ for k:=i-1 downto i-y do∙ if data[k,j,1]-1<xx then xx:=data[k,j,1]-1; ∙ for k:=j-1 downto j-x do∙ if data[i,k,2]-1<yy then yy:=data[i,k,2]-1; ∙ t:=0;∙ for k:=i-y to i do∙ t:=t+b[k,j]-b[k,j-xx-1];∙ if max1<t then max1:=t;∙ t:=0;∙ for k:=i-yy to i do t:=t+b[k,j]-b[k,j-x-1];∙ if max1<t then max1:=t; ∙ end;∙ d[i,j]:=max1;∙ if max<max1 then max:=max1; ∙ end;∙ writeln(max);∙end.【动态规划进阶】商店购物(IOI1995)Time Limit:10000MS Memory Limit:65536KTotal Submit:13 Accepted:6Description某商店中每种商品都有一个价格。

最大公共子序列的算法
最大公共子序列（LCS）问题是一个经典的计算机科学问题，它涉及到两个序列的匹配问题。

给定两个序列，找出最长的公共子序列，使得这个子序列在两个输入序列中都出现。

下面是一种常用的动态规划算法来解决这个问题：
1.初始化两个矩阵，分别表示两个输入序列的长度。

假设输入序列A的长度为m，输入序列B的长度为n，那么这两个矩阵的大小都为m x n。

2.填充矩阵的第一行和第一列。

对于矩阵的第一行，所有的元素都设置为0，因为子序列不能在原序列之前开始；对于矩阵的第一列，所有的元素都设置为1，因为第一个字符总是匹配的。

3.从矩阵的第二行和第二列开始，遍历矩阵的每一个元素。

如果当前元素对应的两个字符相同，那么该元素的值就等于左上角元素的值加1；否则，该元素的值就等于左上角元素的值。

4.填充完矩阵之后，最大公共子序列的长度就等于矩阵右下角的元素的值。

5.回溯矩阵，从右下角开始，找到最长公共子序列。

如果当前元素的值等于左上角元素的值加1，那么将当前字符添加到最长公共子序列中，然后继续向左上方移动；如果当前元素的值等于左上角元素的值，那么不将当前字符添加到最长公共子序列中，继续向左上方移动。

6.当回溯到左上角时，最长公共子序列的长度就等于左上方元素的值。

这个算法的时间复杂度是O(mn)，其中m和n分别是两个输入序列的长度。

在实际应用中，如果输入序列的长度很大，可以考虑使用其他优化算法来提高效率。

IOI2010中国国家集训队作业解题报告最大收益How to Get the Maximum Income解题报告中山市第一中学冯齐纬目录目录 (1)题目描述 (3)问题分析 (4)算法一.直接搜索 (4)算法二.搜索+二分图匹配 (4)算法三.最大权二分图匹配 (5)算法四.离散化+最大权二分图匹配 (6)算法五.贪心+离散化+二分图匹配 (9)算法六.贪心+堆 (11)算法七.贪心+离散化+线性匹配 (11)算法七的一点优化 (13)数据生成与测试结果 (15)更优的算法 (19)题目模型 (20)附录 (22)对命题二的证明 (22)求出所有活跃点的算法A (24)算法一的程序实现 (24)算法二的程序实现 (25)算法三的程序实现 (27)算法四的程序实现 (29)算法五的程序实现 (32)算法六的程序实现 (33)算法七的程序实现 (36)算法七优化后的程序实现 (38)感谢 (41)题目描述给出N件单位时间任务，对于第i件任务，如果要完成该任务，需要占用[Si, Ti]间的某个时刻，且完成后会有Vi的收益。

求最大收益。

N≤5000，1 ≤ Si ≤ Ti ≤ 108，1 ≤ Vi ≤ 108。

澄清：一个时刻只能做一件任务，做一个任务也只需要一个时刻。

下面举一个样例说明。

样例输入样例输出样例说明41 1 22 2 2 1 23 1 3 16 共有四个任务，其中第一个任务只能在时刻1完成，第二个任务只能在时刻2做，第三个任务只能在时刻1或时刻2做，第四个任务可以在[1,3]内任一时刻完成，四个任务的价值分别为2、2、3和1。

一种完成方案是：时刻1完成第一个任务，时刻2完成第三个任务，时刻3完成第四个任务，这样得到的总收益为2+3+1=6，为最大值。

问题分析算法一·直接搜索看到题目，我们能立即得到一个正确的算法：由于每件任务只能在指定区间的时刻完成，对每个任务i，我们不妨枚举它做与否，如果做再枚举Si到Ti中的某个未占用时刻来完成它，同时标记所有的时刻是否被占用。

求最大子矩阵的两种思路长沙市雅礼中学贺一骏编者：求最大子矩阵问题是很常见的一类问题，具有很强的代表性，通过这个问题，可以派生出更加复杂的问题，也可以学到很多常用的问题处理手段。

问题描述一个被分为n*m个格子的月饼盒，第i 行第j 列位置的格子里面有a [ i , j ]个月饼。

本来CCC老师打算送这盒月饼给某人的，但是就在要送出月饼盒的前一天晚上，一只极其可恶的老鼠夜袭月饼盒，有部分格子被洗劫并且穿了洞。

CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒，新的月饼盒不能有洞，并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。

任务：请帮CCC老师设计一个程序，计算一下新月饼盒最多能够保留多少月饼。

输入文件的第一行有两个整数n、m。

第i + 1 行的第j 个数表示 a [ i , j ]，如果这个数为0 ，则表示这个位置的格子被洗劫过。

其中：1 ≤n，m ≤300，0 ≤a [ i , j ]≤255输出在文件中写入最大月饼数。

样例Sample Input3 41 2 3 45 06 310 3 4 0Sample Output17分析该问题实际上是求在给定平面区域中找出一个最大的子矩形，要求该矩形不能包含某些限定的格子。

方法一：我们初次见到这个问题，可能最直接的想法就是枚举。

即枚举每个矩阵的左上角坐标（x1,y1）和右下角坐标(x2,y2)，然后统计这个矩阵是否满足题设条件。

我们可以先预处理从左上角（1,1）出发到任意一点（i,j）的月饼数目area(i,j)，预处理的时间复杂度为O(mn),程序如下：For i:=1 to n doFor j:=1 to m doArea[I,j]:=area[i-1,j]+area[i,j-1]-area[i-1,j-1]+mooncake[i,j];其边界条件为area[0,i]=0,area[i,0]=0Mooncake[i,j]表示(i,j)这个点的上月饼数目，如果(i,j)这个点被破坏，则设mooncake[i,j]=-30000000，那么有area[i,j]<0。

最长公共子序列最优解作为一名小学生，这个题目对我来说好难呀，我不太懂什么是“最长公共子序列最优解”呢！这好像是一个很复杂很神秘的知识，就像宇宙中的黑洞一样让人摸不着头脑。

老师在课堂上讲这个的时候，同学们有的皱着眉头，有的咬着笔杆，都在努力思考。

我心里想：这到底是个啥呀？怎么这么难理解？我去问同桌：“你懂这个最长公共子序列最优解吗？”同桌一脸迷茫地摇摇头说：“我也不懂啊，感觉像是一道超级难题！”然后我又去问学习好的班长，班长扶了扶眼镜说：“这个呀，就是要找到两个序列中相同的部分，而且要让这个相同的部分最长，还要是最优的那种。

”我听了还是有点迷糊，就问：“那怎么才能找到呢？”班长说：“这就得用一些方法和算法啦，比如说动态规划。

”我惊讶地张大了嘴巴：“动态规划？那又是什么呀？”回到家我赶紧问爸爸妈妈，爸爸说：“孩子，这就好比我们找宝藏，要在很多很多的地方找，还得找到最好最多的那一份。

”妈妈接着说：“对呀，就像我们去超市买东西，要在一堆商品里挑出性价比最高的。

”我好像有点明白了，可是又不是完全懂。

我想，这个最长公共子序列最优解难道是个会变魔法的精灵，总是躲躲藏藏，不让我们轻易找到它？后来老师又给我们举了好多例子，我慢慢地好像能跟上一点思路了。

可还是觉得好难好难，这不就像爬山，好不容易爬了一段，抬头一看，还有好长好长的路要走。

哎呀，我什么时候才能真正搞懂这个最长公共子序列最优解呀！我觉得我一定要努力，就像战士攻克城堡一样，一定要把这个难题拿下！我觉得学习就是一场冒险，每一个新知识都是一个神秘的岛屿等着我们去探索。

虽然这个最长公共子序列最优解现在让我很头疼，但我相信，只要我坚持，总有一天能搞明白的！。

2022年职业考证-软考-软件设计师考试全真模拟易错、难点剖析AB卷（带答案）一.综合题(共15题)1.单选题n个关键码构成的序列{k1,k2, ...Kn}当且仅当满足下列关系时称其为堆。

以下关键码序列中，（）不是堆。

问题1选项A.15,25,21,53,73, 65,33B.15,25,21,33,73,65,53C.73,65,25,21,15,53,33D.73,65,25,33,53,15,21【答案】C【解析】本题考查堆排序的算法问题。

堆分为大顶堆（根节点大于左孩子和右孩子节点）和小顶堆（根节点小于左孩子节点和右孩子节点）。

根据选项来看，共7个节点，应该是3层的满二叉树，符号堆的有A，B，D三个选项。

仅有C选项73,65,25,21,15,53,33，73作为根节点，根大于其左孩子节点65和右孩子节点25都，是大顶堆的构造，第二层65作为左子树的根节点，大于了其左孩子节点21和右孩子节点15，符合大顶堆的构造；25作为右子树的根节点，却小于了其左孩子节点53和右孩子节点33，不符合大顶堆的构造了，故其不是堆。

2.单选题对高级程序语言进行编译的过程中，使用（）来记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成。

问题1选项A.决策表B.符号表C.广义表D.索引表.【答案】B【解析】考查分析语义分析阶段相关问题。

语义分析阶段主要是分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息提供后面的代码生成阶段使用。

在确认源程序的语法和语义后，可以对其进行翻译并给出源程序的内部表示。

对于声明语句，需要记录所遇到的符号的信息，所以应该进行符号表的填查工作，用来记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成。

至于决策表是用于测试的，广义表是针对数据结构的表示，索引表是数据库中指示逻辑和物理记录对应的关系。

3.单选题如下图如下E-R图中，两个实体R1、R2之间有一个联系E，当E的类型为（）时必须将E转换成—个独立的关系模式？问题1选项A.1:1B.1:*C.*：1D.*： *【答案】D【解析】本题考查的是E-R转换为关系模式的转换规则。

解题报告POJ2935Basic Wall MazeTime Limit: 1000MS Memory Limit: 65536KDescriptionIn this problem you have to solve a very simple maze consisting of:1. a 6 by 6 grid of unit squares2. 3 walls of length between 1 and 6 which are placed either horizontally or vertically toseparate squares3.one start and one end markerA maze may look like this:You have to find a shortest path between the square with the start marker and the square with the end marker. Only moves between adjacent grid squares are allowed; adjacent means that the grid squares share an edge and are not separated by a wall. It is not allowed to leave the grid.InputThe input consists of several test cases. Each test case consists of five lines: The first line contains the column and row number of the square with the start marker, the second line the column and row number of the square with the end marker. The third, fourth and fifth lines specify the locations of the three walls. The location of a wall is specified by either the position of its left end point followed by the position of its right end point (in case of a horizontal wall) or the position of its upper end point followed by the position of its lower end point (in case of a vertical wall). The position of a wall end point is given as the distance from the left side of the grid followed by the distance from the upper side of the grid.You may assume that the three walls don’t intersect with each other, although th ey may touch at some grid corner, and that the wall endpoints are on the grid. Moreover, there will always be a valid path from the start marker to the end marker. Note that the sample input specifies the maze from the picture above.The last test case is followed by a line containing two zeros.OutputFor each test case print a description of a shortest path from the start marker to the end marker. The description should specify the direction of every move (‘N’ for up, ‘E’ for right, ‘S’ for downand ‘W’ f or left).There can be more than one shortest path, in this case you can print any of them.Sample Input1 62 60 0 1 01 5 1 61 5 3 50 0Sample OutputNEEESWW简单的迷宫问题(Basic Wall Maze)题目描述：在本题中，你需要求解一个简单的迷宫问题：1) 迷宫由6行6列的方格组成；2) 3堵长度为1～6的墙壁，水平或竖直地放置在迷宫中，用于分隔方格；3) 一个起始位置和目标位置。

poj1083解题报告（poj1083analysisreport）题⽬⼀层⾥⾯有400个房间，北边和南边各有200个房间，要从⼀个房间⾥⾯把⼀张桌⼦移动到另⼀个房间，需要占⽤这两个房间之间的所有⾛廊（包括这两个房间前⾯的），每移动⼀个桌⼦需要10分钟，给出需要移动的桌⼦的数据（从哪移动到哪），要求计算出最少需要多少分钟才能把所有桌⼦移动完。

分析题很简单，但是⼀定要看题⽬⾥⾯的那个图。

要注意的只有⼀点，房间1和2前⾯是同⼀个⾛廊，所以从1移动到2只需要占⽤⼀个⾛廊，房间2和3前⾯不是同⼀个⾛廊，因此从2移动到3需要占⽤2个⾛廊。

基本思路是开辟⼀个200的数组，表⽰所有房间前⾯的⾛廊，每个元素初始化为0，如果从m移动到n（假设m<n，但是在程序中处理输⼊时需要判断两个数⼤⼩），则把序号为(m-1)/2到（n-1）/2的所有数组元素都+10，这样处理完每个桌⼦后，遍历整个数组寻找最⼤的⼀个元素，即为实际的需要时间。

代码#include<stdlib.h>#include<stdio.h>#include<string.h>int main(){int n,tables,corridor[200],i,j,start,end,time,x,y;scanf("%d",&n);while(n-->0){memset(corridor,0,sizeof(corridor));time=0;scanf("%d",&tables);for(i=0;i<tables;i++){scanf("%d%d",&x,&y);start=((x<y?x:y)-1)/2;end=((x>y?x:y)-1)/2;for(j=start;j<=end;j++)corridor[j]+=10;}for(i=0;i<200;i++)time=corridor[i]>time?corridor[i]:time;printf("%d\n",time);}return0;}。

珠宝给一棵n个结点的树，给每个点安排一个正整数编号，使得相邻点具有不同的编号，编号的总和尽量小。

输入第一行：n(n<=50,000)以下n-1行，每行两个数u,v(1<=u,v<=n)，表示u 和v有一条边输出仅一行，为最小编号和样例输入81 21 31 41 55 65 75 8样例输出11分析：看完题目，很自然地联想到树型DP，而且也不难得到状态表示方法。

先根据输入的数据构造出一棵树，然后从树的叶子结点往上倒推。

设F[I，J]表示以I为根的子树在I的编号为J时，可以得到的最小编号和。

状态转移方程为：F[I，J] = Min{∑F[I1, J1]} + J其中I1表示I的一个子结点编号，J1为不同于J的一个自然数。

很显然，在最优方案中，所有解的编号都是不可能超过N的。

因此不难推出算法的时间复杂度为O（N^3）,空间复杂度为O（N^2）。

这对于本题的规模来说，是无法承受的。

分析一下几个比较小的数据，会发现在最优方案中，最大的编号全部都没有达到N，不妨设其为M。

而且凭感觉来看，M比N要小很多。

很自然地，我们会考虑计算出这个比N小的M，然后DP的时候只要对每个点考虑编号为1到M的状态即可。

这样时间复杂度就降为O（NM^2），空间复杂度降为O（NM）。

但是M究竟怎么得到呢？我们发现这是很难计算的，而且也不太好估算出一个界（至少我没有想到好的方法）。

事实上可以采取一种比较无奈的方法。

因为N 最大为50000，时限为1S，所以要想算法在理论上的最坏情况下不超时，M取30左右比较保险，实践证明，M取30足以通过所有测试数据了。

似乎通过上面的分析本题已经解决得差不多了，但M毕竟是“贪”出来的，正确性不能得到理论上的证明，我们不妨从算法优化的角度来考虑这个问题。

还是回到最初的DP算法。

仔细推敲一下就会发现，F[I，1 .. M]这M个状态中，能够在以后的状态转移中真正利用到的只有两个，它们是这M个状态中值最小的两个。

大林算法习题答案大林算法习题答案大林算法是一种常用于解决复杂问题的算法，它的应用范围广泛，可以用于优化、搜索、模拟等领域。

它的核心思想是将问题分解成多个子问题，并通过递归的方式解决每个子问题，最终得到整体的解答。

下面将通过几个具体的习题来解释大林算法的应用。

习题一：背包问题假设有一个背包，它的容量为C，有n个物品，每个物品的重量分别为w1,w2, ..., wn，价值分别为v1, v2, ..., vn。

要求在不超过背包容量的前提下，选择一些物品放入背包，使得背包中物品的总价值最大。

这是一个经典的背包问题，可以用大林算法来解决。

解答：首先，我们可以将问题分解成两个子问题：选择第n个物品放入背包和不选择第n个物品放入背包。

如果选择第n个物品放入背包，那么背包的容量就减少了wn，总价值就增加了vn；如果不选择第n个物品放入背包，那么背包的容量和总价值都不会发生变化。

接下来，我们可以通过递归的方式解决每个子问题。

假设f(i, j)表示在前i个物品中选择一些物品放入容量为j的背包中，使得总价值最大，那么我们可以得到以下递推公式：f(i, j) = max{f(i-1, j), f(i-1, j-wi) + vi}其中，f(i-1, j)表示不选择第i个物品放入背包，f(i-1, j-wi) + vi表示选择第i个物品放入背包。

最终，通过计算f(n, C)，我们就可以得到背包问题的最优解。

习题二：旅行商问题旅行商问题是一个著名的组合优化问题，它的目标是找到一条路径，使得旅行商可以依次访问n个城市并回到起点，同时总路径最短。

这个问题可以用大林算法来解决。

解答：首先，我们可以将问题分解成多个子问题：选择第n个城市作为路径的最后一个城市和不选择第n个城市作为路径的最后一个城市。

如果选择第n个城市作为路径的最后一个城市，那么路径的长度就增加了从前一个城市到第n个城市的距离；如果不选择第n个城市作为路径的最后一个城市，那么路径的长度不会发生变化。