题解 P1736 【创意吃鱼法】
panda_2134
2017-08-05 21:57:42
DP+扫描法
首先给这个题分个类,方便发散思维。
这是一个二维平面上的dp,类似于最大子矩阵。我们试着用类似的思路思考。
二维平面上dp一般采用定区域左下/右下角,在这个点的周围寻找限制条件。
定义$$f(i,j,0)$$为以(i,j)为右下角的矩阵主对角线(左上->右下)合法最大长度。
于是显然有$$f(i,j,0)\leq f(i-1,j-1,0) + 1$$
技巧:把方块0绕着限制的区域转一圈。
![](https://cdn.luogu.com.cn/upload/pic/6782.png)
然后我们就发现,$$f(i,j,0)$$还会受到$$(i,j)$$左侧和上方的最靠近它的那个1限制。
因为$$f(i-1,j-1,0)$$所代表的矩阵一定合法,所以考虑这个限制就可以保证$$f(i,j,0)$$合法,也就是除了主对角线之外没有其他地方有1。
因而就有$$f(i,j,0)\leq \min\{j-a_i,i-b_j\}$$,其中$$a_i$$是左侧最靠近当前位置的1的纵坐标
,$$b_j$$是上方最靠近当前位置的1的横坐标。扫描法维护即可,一边dp一边维护。
副对角线的情况完全类似,自己推一下好了233
不过有几点需要特别注意,见代码里面的注释。尤其是数组,dp用的数组我最开始开的2500\*2500\*5,最后一维大了点,而且交之前算的时候还忘了乘上int的4字节,直接MLE。。。
跑的还是挺快的,最后一个点303ms,总共1051ms
···cpp
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#define REP(i,n) for(int i=1;i<=n;i++)
#define PER(i,n) for(int i=n;i>=1;i--)
#define CLEAR(x) memset(x,0,sizeof(x))
using namespace std;
const int MAXN=2500;
int N,M,ans,opt[MAXN+10][MAXN+10][2],a1[MAXN+10],b1[MAXN+10],a2[MAXN+10],b2[MAXN+10];
//大数组后面加小下标,开大多少要注意!
bool mp[MAXN+10][MAXN+10];
int readint(){
int f=1,r=0;char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)){
r=r*10+c-'0';
c=getchar();
}
return f*r;
}
inline bool Init() {
N=M=ans=0;
CLEAR(opt);CLEAR(mp);CLEAR(a1);CLEAR(a2);CLEAR(b1);CLEAR(b2);
if(scanf("%d%d",&N,&M)<2) return false;
REP(i,N) REP(j,M) mp[i][j]=readint();
return true;
}
inline void Work() {
//一边dp一边刷数组
REP(i,N) REP(j,M)
if(mp[i][j]) {
opt[i][j][0]=min(opt[i-1][j-1][0]+1,min(j-a1[i],i-b1[j]));
a1[i]=j,b1[j]=i;
}
REP(i,N){
a2[i]=M+1;//扫描法一定要多想初值!是否应该为0!找出所有情况下的数据,手算一下
PER(j,M)
if(mp[i][j]) {
opt[i][j][1]=min(opt[i-1][j+1][1]+1,min(i-b2[j],a2[i]-j));
//如果不是必须的话不要省去数组,尤其是扫描法,
//多次使用的滚动数组需要从头再开!因为扫描后值被破坏了!
a2[i]=j,b2[j]=i;
}
}
REP(i,N) REP(j,M) ans=max(ans,max(opt[i][j][0],opt[i][j][1]));
printf("%d\n",ans);
}
int main() {
while(Init()) Work();
}
···
```