题解 P1736 【创意吃鱼法】

滚动数组！滚动数组！滚动数组！ 首先DP思路很清楚了，dp[i][j]表示右至左到i,j的最大值，f[i][j]表示左至右到i,j的最大值 ~~鱿鱼~~由于空间吃紧，我决定利用滚动数组，同样，left[i][j]表示i,j左边连续0的个数（包括自身），right[i][j]同理，up[i][j]亦然 可以发现left[i][j]和right[i][j]只与本行有关，所以直接一维搞掉 up[i][j]和上一行有关，用滚动即可，dp和f同理 方程其他题解讲得很清楚了，我主要讲滚动 附方程（以dp为例）： dp[i][j]=min(dp[i-1][j+1],min(right[i][j+1],up[i][j]))+1; 优化后：dp[j]=min(dp[j+1],min(right[j+1],up[j]))+1; ## 最后注意！要反着来！要反着来！要反着来！ 丢代码预警 ------------ ```cpp #define maxn 3000+50 #include<cstdio> #include<algorithm> #include<cstring> #include<cctype> using namespace std; int a[maxn],f[maxn],dp[maxn],left[maxn],right[maxn],up[maxn]; inline void read(int &x) //快读，不用会炸 { x=0; char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); } int main() { int n,m,ans=0; read(n); read(m); memset(up,0,sizeof(up)); //由于up与上一行有关所以开头memset，f和dp同理 memset(f,0,sizeof(f)); memset(dp,0,sizeof(dp)); for (int k=1;k<=n;++k) { memset(left,0,sizeof(left)); //这两个只与当前行有关，分别初始化 memset(right,0,sizeof(right)); for (int i=1;i<=m;++i) { read(a[i]); //读入当前行 if (a[i]) left[i]=0; else left[i]=left[i-1]+1; //计算left } for (int i=m;i>0;--i) if (a[i]) right[i]=0; else right[i]=right[i+1]+1; //计算right for (int i=m;i>0;--i) //注意！反着来 if (a[i]) { f[i]=min(f[i-1],min(left[i-1],up[i]))+1; //方程 ans=max(ans,f[i]); } else f[i]=0; for (int i=1;i<=m;++i) if (a[i]) { dp[i]=min(dp[i+1],min(right[i+1],up[i]))+1; //方程 ans=max(ans,dp[i]); } else f[i]=0; for (int i=1;i<=m;++i) if (a[i]) up[i]=0; //最后计算up值，因为第一行的up值全为0 else up[i]++; } printf("%d",ans); return 0; } ```