写在前面:

一天前:

两天啃完吧,重要的是真正学会这个知识点,特意放慢脚步……前两天一天一个小专题真是搞得太紧张,好多都没有弄太懂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—i1—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;
}