## 题目2 Circuit Board
这个在LeetCode上的84 是个经典问题。LeetCode我都还只做到了.. 反正很少的,也没有接手Hard，easy感觉总是水水过去，medium也很少很少。 下一步说不定可以在github上维护一下？分单独的题解和分开的题解……完全可以在幕布上写了再移植过去的。（心情复杂.jpg）也可以不移植### 题意
300*300矩阵，给定一大堆数字，使得每行中的最大值、最小值的差不超过K，满足这些条件的最小子矩阵是多少。### false （大部分false的删了……）
o（n^3)的做法。 开始想的是并查集归属，串串儿一样噜过去，但是其实有点emmmm 对于这样的情况，只连续的找到个体然后从个体开始蔓延是不行的。 2 2 2 4 4 2 2 2 2 2 2 4 有种感觉，你需要抛开种族偏见，不能这样狭隘的去想，而且n很小，可以直接枚举两维，再来一维 首先呢，我们用一个三维布尔数组来记录，f[i][l][r]，记录的是i行的从 l 处到 r 处，此段里能否达到"不超过E"的条件。 这里是很死板的，甚至不用考虑最大值如果有两个的问题，只需预处理，枚举l和r。 好。如果布尔类型已经确定了### 布尔怎么更新？
想了想，还是要至少更新n*(n-1)/2个。 那真的好笑。如果跟前面比是可，然后大小都没越界， 当前我在的位置是a2，当前已有len匹配到了(算了a2) ，那么1~ a2-len填No，a2-len+1 ~ a2填Yes（true）。 大小越界怎么看呢？ 嗯，这个好像也是有时效性的，用最笨 的办法，那不如 满足K的时候正着来，不满足的时候1~a2-len+1依然可，后面一边走一边维护tmpmax和tmpmin 再想。 如果直接维护l和r呢？ 嗯，这里，思维的差距就体现出来了。我们我在上面写的方法可以是可以，但是相当麻烦，而且有没有感觉到，有一种"特殊化"的感觉。 抛开这些再想想，在本文末尾，有提供一维怎么解答，可以nlogn，但没必要。 这个处理是和主程序分开写的，完全可以分开写，枚举的意思就是... 直接暴力的l和r，哪怕n^2的直接跑一遍，每次只看一个名为“l到r"的区间，只写一个false or true。即使这样n平方复杂度也足够了 剥离出来统一的看，思维要上升一个高度。。### true =================================
我觉得好蠢哦，上面可以验证都是false的，高度根本不用管。 与其这样写题解，还是自己捋顺了是最好的吧…… …………………… 这个题只有一句话。枚举l和r，那么这个串串的宽度是确定的，l和r已经n^2了 宽度确定后，到底有多长，就直接判断yes和no，然后使用累加，再乘以r-l+1就可了。 为什么要这么做？题中说要验证最长的块，那么是长度（横着）确定，去竖着撸一下更好呢，还是竖着确定，横着撸一串最好呢 显然，应该长度确定，然后看有几行能符合这个条件。直接一行一行看就可以了（图一） 如果是宽度确定的话，即使是继续扩展，是没用的，因为并不是以这个作区分的，可以看到1 1 3 这样按照这种划分方式并不能说明，因为这也不是题目的本意。（图二）99 3 4 0 2 2 2 3 3 2 2 2 2 2 2 3 26分到手…… 思路理清之后，是没问题的，只是我写错了一个== ， 一个就是更新的时候没把1,1这样的首部更新进去 关键是思路啊！！！这还是很简单的啊！！！！26分啊！！！！kickstart错过就没了啊啊啊啊！！！ 最后粘一下代码
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n;
bool f[305][305][305];
int a[305][305];
int a1, a2, k;
int main() {
int t; cin >> t;
int kase = 0;
while (t--) {
//f好像不用清空 直接初始化就好
//输入
cin >> a1 >> a2 >> k;
for (int i = 1; i <= a1; i++) {
for (int j = 1; j <= a2; j++) {
cin >> a[i][j];
}
}
//对数据处理 初始化bool f
bool ff; int now;
for (int i = 1; i <= a1; i++) {//行
for (int left= 1; left <= a2; left++) { //下面的列
f[i][left][left] = true;
int maxx = a[i][left]; int minn = a[i][left];
//【惊！我这里多写了个等号】
//【惊！2 我忘记把第一个考虑进去！了耶】
ff = true;
for (int right = left+1 ; right <= a2; right++) {
if (ff == false)f[i][left][right] = false;
else {
now = a[i][right];
maxx = max(maxx, now);
minn = min(minn, now);
if (minn + k<now ||maxx-k>now)
ff = false;
f[i][left][right] = ff;
}
//这个数和minn maxx比较一下就好了 同时更新一下
// 如果已经是false了 那就全盘都是false好l
}
}
}
/*
for (int i = 1; i <= a1; i++) {//行
for (int left = 1; left <= a2; left++) { //下面的列
for (int right = left; right <= a2; right++) {
cout << f[i][left][right]<<" ";
}
cout << endl;
}
cout << endl;
}
*/
int maxans = -1;int ans = 0;
// ... 好.. 那处理完了还剩一次最后的循环和拍
for (int l = 1; l <= a2; l++) {
for (int r = l; r <= a2; r++) {
ans = 0;
for (int i = 1; i <= a1; i++) {
if (f[i][l][r] == true) {
ans += (r - l + 1);
maxans = max(ans, maxans);
}
else {
ans = 0;
}
}
}
}
cout <<"Case #"<<++kase<<": "<< maxans << endl;
}
return 0;
}
### 变形
但就是说这样题目是个有名的变形，还有：这个是... 饿示意图.. 这个题目的意思相当于是让我们这样求。实际上可以转化到leetcode的这样题目：