题解 P1736 【创意吃鱼法】

panda_2134

2017-08-05 21:57:42

Solution

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