hnust_zhouzisheng

题解

算法(3)

/ 注册

全部文章 / 题解（共27篇）

【每日一题】 Max Power

题意：一个技能树一共有n行，第i行有n-i+1个技能，要学习第i行第j列技能的前提是学习第i-1行第j列和j+1列的技能，每个技能会带来一定收益。问给定技能的最多学习次数，能够得到的最大收益是多少。思路：dp。将技能的收益按如下格式列出：1 2 3 4 51 2 ...

2020-08-07

0 557

【每日一题】 [CQOI2007]涂色PAINT

题意：对于一段空白的木板，每次可以选取连续的一段涂上任意中颜色，问将木板涂至给定颜色需要的最少次数。思路:区间dp。原问题：将木板全部涂色完成需要的最少次数。子问题：将木板的连续某一段涂完需要的最少次数。记：dp[i][j]表示将木板的第i块至第j块涂成指定颜色需要的最少次数。区间dp考虑先枚举...

2020-08-07

0 670

【每日一题】乌龟棋

动态规划一道很正的动态规划题，直接进行分析：原问题：选取所有卡片到最后一个格子是能够得到的最大分数；子问题：四种卡片分别选i,j,k,l张时能得到的最大分数；记dp[i][j][k][l]为四种卡片分别选出了i,j,k,l张时能够取得的最大分数。有的人可能会按“前i个格子如何选取卡片”类似这样的...

2020-07-24

0 626

【每日一题】小A的柱状图

单调栈本题要求找出最大矩形的面积。从基本概念入手，给定长（本题也可以说“高”）和宽便可以确定一个矩形的面积，所以我们的任务便是找到高和宽。首先，要尝试所有的区间很显然是不可能的；可以发现对于每一段区间，矩形的宽都可以用a数组的前缀和求出来，所以我们的任务重心转移到了矩形的高上。求高便是求一段区...

2020-07-24

0 467

【每日一题】区间权值

前缀和首先说明一下题目中的要求值的式子的意思：对于所有的区间[l,r]（其中1<=l<=r<=n），求每个区间点对应的数的和（即a[i]的和），将其乘以区间的长度对应的权值（即w[r-l+1]），取和并输出。理解了上述之后，毫无疑问此题需要用前缀和，解决此题有两种处理途径：枚举...

2020-07-20

0 1011

【每日一题】点权和

首先，考虑一下常规思路，每次将操作数和与操作数相连的点的权值都加一，然后计算值。显然这种思路的会TLE。不过我们可以发现，这种思路其实不止适用于树，还适用于图。如此我们便要思考，就本题而言，树与图有什么区别。树型结构为一对多的关系，不像图的多对多，这使得我们可以从树中找到节点的祖宗及后代，因此我们要...

2020-07-16

0 572

【每日一题】 [SCOI2009]生日快乐

递归数据范围较小，直接递归解决。考虑将当前蛋糕分成left块：当left==1时，返回长与宽的比值；当left>1时，若沿着当前蛋糕的某一条边切割总共有n/2种切割方法（考虑对称性），沿着长和宽总共有(n/2)*2种切割方法；对于当前蛋糕的每一种切割方法，递归考虑其切割后的两个蛋糕，得到二者...

2020-07-15

0 607

【题解】 [AHOI2007]密码箱

数论。题意：给定一个正整数n，要求找到所有在[0,n)之间的整数x满足：%n=1。思路：%n=1可以写作=nk+1，即：(x-1)(x+1)=nk。拆分x与k得到：(x-1)(x+1)=(n1k1)(n2k2)，所以有：x-1=n1k1、x+1=n2k2。接下来当n1<=n2时，可以在时间...

2020-07-12

2 516

【每日一题】 kingdom

动态规划。根据题意直接构造出树比较难，所以采用动态规划的方法。记ans[i]表示当树有i个结点时所求花费的最大值。假设在考虑有i个结点时，我们已经知道了结点数小于i时的ans，则可以通过ans[i]=max(ans[i],ans[j]+???)得到答案，其中j为结点数为i时所有可能的重儿子，也就...

2020-07-10

1 779

【每日一题】矩阵取数游戏

区间dp。首先，由题意，每行取数独立，因此可以分别分析每一行的情况。其次，基础的区间dp。原问题：从序列第1个数到第m个数取出后的答案子问题：从序列第i个数到第j个数取出后的答案记dp[i][j]表示从序列中第i个数到第j个数取出后的答案，得到转移方程：dp[i][j]=max(dp[i+1][...

2020-07-10

0 496