题解 P1736 【创意吃鱼法】

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绕着限制的区域转一圈。

然后我们就发现,$$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

#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();
}
···