二维动态规划
写在前面:
一天前:
两天啃完吧,重要的是真正学会这个知识点,特意放慢脚步……前两天一天一个小专题真是搞得太紧张,好多都没有弄太懂QAQ
一天后:
QAQ说好的两天的,结果一天都搞完了,mmp,可能是题目比较水的原因吧,大多都是自己认真想出来的,有时候对于题目的理解不太对,导致自己一直想不对,比如P1295创意吃鱼,我这语文理解能力啊QAQ太弱了……
P1295创意吃鱼
题目描述:
- 可爱猫猫家里长方形大池子中有很多鱼,她开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法 。她发现,把大池子视为01矩阵(0表示对应位置无鱼,1表示对应位置有鱼)有助于决定吃鱼策略。
- 在代表池子的01矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线的一端”下口,只一吸,就能把对角线上的那一队鲜鱼吸入口中。
- 猫猫是个贪婪的家伙,所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下,她一口下去,最多可以吃掉多少条鱼?
输入:
第一行有两个整数n和m(n,m≥1),描述池塘规模。接下来的n行,每行有m个数字(非“0”即“1”)。每两个数字之间用空格隔开。
输出:
只有一个整数——猫猫一口下去可以吃掉的鱼的数量,占一行,行末有回车。
题解:
这道题,首先你需要正确的理解题意,表示如果喵喵要吃鱼鱼的话,就要让对角线上的全部都是鱼鱼才能够被吃掉的说(理解错题意然后手推两个小时乱子都没有推出来的弱鸡)。然后对角线有两种,分别是左上到右下,和右上到左下,所以需要处理两次。
然后这道题我们要明白,在对角线所在的矩阵中,除了对角线意外的地方不能有鱼,QAQ奇怪的设定。我们所设置的状态 f[i][j]
表示的是在以横坐标为i,纵坐标为j的对角线末端所能够吃到的最大的鱼鱼的数量。
然后就开始找关系了,对于 f[i][j]
可以从 f[i-1][j-1]
来推过来,如果 f[i][j]
为没有鱼,我奉劝你continue,如果有鱼,就开始和 f[i-1][j-1]
进行对接,但是仔细想一想,如果在 f[i][j]
相同一行或者一列的,在 f[i-1][j-1]
所形成的最大鱼鱼数范围之内有地方有鱼,也就是说在矩阵中除了对角线的地方还有其他地方有鱼,那么就是不成立的,但是我们怎样找到最大的成立矩阵呢。
这个我们就需要进行预处理了(预处理大法好!),然后我们可以建立数组 Up[i][j]
, Left[i][j]
,和 Right[i][j]
这三个数组,分别表示在i,j这个位置上,Left/Right/Up
(左边/右边/上边)连续0(没有鱼)的长度,这样我们在判断矩阵的大小的时候,选择的是这三个值的最小值—— Left/Right/Up/f[i-1][j-1]
(当对角线为左上到右下的时候为 Left/Up/f[i-1][j-1]
,对角线为右上到坐下的时候为 Right/Up/f[i-1][j-1]
) f[i-1][j-1]
的值就是本身矩阵的长度,所以说最后在成立最大矩阵加上i,j这条鱼,就是 f[i][j]
的最终值!
代码:
1 |
|
P1298矩阵切割
题目描述:
森炊很喜欢巧克力,也很喜欢正方形,但是并不是所有他想吃的巧克力都是正方形的,对于一个长方形的巧克力来说,森炊会把他掰成若干个正方形巧克力来吃,现在他买了一块巧克力,他想知道在把巧克力吃完的前提下,至少能吃到多少块正方形巧克力。由于森炊是一个耿直的人,他掰巧克力的方向只会与巧克力的边平行,不会发生斜着掰巧克力的情况
输入:
输入文件中包含两个正整数,代表矩形巧克力的边长,每边长均在1—100之间。
输出:
输出文件包含一行,输出森炊最少能吃到多少块正方形巧克力。
题解:
这道题不少人看到题就开始想贪心,只要能让子正方形越大越好……
QAQ太天真了……而且这种贪心可能可以过几组小数据,坑人啊……
这道题请看数据范围(100!!!),好的四重循环以内,想必你已经猜测出来了,我们建立数组 f[i][j]
表示长为i,宽为j的矩阵里面包含的最小正方形的个数,然后我们就可以想如何从小推到大了。
首先我们一个大问题是由子问题推出来的,子问题是什么呢,想必看到四重循环就明白差不多了吧,我们再次开一个两重循环,枚举 1—i
和 1—j
,表示一个分割点,把矩阵 i-j
通过最新枚举的中间点分割为4个子矩阵,然后用子矩阵加起来更新 f[i][j]
最后输出 f[n][m]
答案就好。
充分说明了看数据范围的重要性!
代码:
1 |
|