写在前面：

一天前：

两天啃完吧，重要的是真正学会这个知识点，特意放慢脚步……前两天一天一个小专题真是搞得太紧张，好多都没有弄太懂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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,a[3000][3000];
int f[3000][3000],ans=0,Up[3000][3000];
int Right[3000][3000],Left[3000][3000];
int main()
{
    ios::sync_with_stdio(false);
    memset(f,0,sizeof(f));
    memset(Up,0,sizeof(Up));
    memset(Left,0,sizeof(Left));
    memset(Right,0,sizeof(Right));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>a[i][j];
        if(a[i][j]==0)
        {
            Up[i+1][j]=Up[i][j]+1;
            Left[i][j+1]=Left[i][j]+1;
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=m;j>=1;j--)
    if(a[i][j]==0)
    Right[i][j-1]=Right[i][j]+1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(a[i][j]==1)
    {
        f[i][j]=min(f[i-1][j-1],Left[i][j]);
        f[i][j]=min(f[i][j],Up[i][j])+1;
        ans=max(ans,f[i][j]);
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=m;j>=1;j--)
    if(a[i][j]==1)
    {
        f[i][j]=min(f[i-1][j+1],Right[i][j]);
        f[i][j]=min(f[i][j],Up[i][j])+1;
        ans=max(ans,f[i][j]);
    }
    cout<<ans<<endl;
    return 0;
}

P1298矩阵切割

题目描述：

森炊很喜欢巧克力，也很喜欢正方形，但是并不是所有他想吃的巧克力都是正方形的，对于一个长方形的巧克力来说，森炊会把他掰成若干个正方形巧克力来吃，现在他买了一块巧克力，他想知道在把巧克力吃完的前提下，至少能吃到多少块正方形巧克力。由于森炊是一个耿直的人，他掰巧克力的方向只会与巧克力的边平行，不会发生斜着掰巧克力的情况

输入：

输入文件中包含两个正整数，代表矩形巧克力的边长，每边长均在1—100之间。

输出：

输出文件包含一行，输出森炊最少能吃到多少块正方形巧克力。

题解：

这道题不少人看到题就开始想贪心，只要能让子正方形越大越好……

QAQ太天真了……而且这种贪心可能可以过几组小数据，坑人啊……

这道题请看数据范围（100！！！），好的四重循环以内，想必你已经猜测出来了，我们建立数组 f[i][j] 表示长为i，宽为j的矩阵里面包含的最小正方形的个数，然后我们就可以想如何从小推到大了。

首先我们一个大问题是由子问题推出来的，子问题是什么呢，想必看到四重循环就明白差不多了吧，我们再次开一个两重循环，枚举 1—i 和 1—j ，表示一个分割点，把矩阵 i-j 通过最新枚举的中间点分割为4个子矩阵，然后用子矩阵加起来更新 f[i][j] 最后输出 f[n][m] 答案就好。

充分说明了看数据范围的重要性！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,f[101][101];
int main()
{
    memset(f,10,sizeof(f));
    cin>>n>>m;
    for(int i=0;i<=max(n,m);i++)
	{
		f[0][i]=0;
		f[i][0]=0;
		f[i][i]=1;
	}
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        for(int k=1;k<=i;k++)
        for(int p=1;p<=j;p++)
        {
            int xx=f[k][p]+f[i-k][p]+f[k][j-p]+f[i-k][j-p];
            f[i][j]=min(xx,f[i][j]);
        }
    }
	cout<<f[n][m]<<endl;
    return 0;
}