洛谷1736（二维dp+预处理）

洛谷1387的进阶版，但很像。

1387要求是“全为1的正方形”，取dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))吧？这个有“只有对角线可以有1”的要求，取的是dp[i][j] = min(dp[i-1][j-1], min(s1[i-1][j], s2[i][j-1]))，s1s2是预处理的两个数组，表示上方和左方有多少连续的0.另外本题左右方向对角线都算，所以得算两遍。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 int n, m, ans, a[maxn][maxn];

 int s1[maxn][maxn], s2[maxn][maxn], dp[maxn][maxn];

 int main() {

     scanf("%d %d", &n, &m);

     for (int i = ; i <= n; i++) {

         for (int j = ; j <= m; j++) {

             scanf("%d", &a[i][j]);

         }

     }

     for (int i = ; i <= n; i++) {

         for (int j = ; j <= m; j++) {

             if (!a[i][j]) {

                 s1[i][j] = s1[i-][j] + ;//up

                 s2[i][j] = s2[i][j-] + ;//left

             } else {

                 dp[i][j] = min(dp[i-][j-], min(s1[i-][j], s2[i][j-])) + ;

                 ans = max(ans, dp[i][j]);

             }

         }

     }

     memset(dp, , sizeof dp);

     memset(s2, , sizeof s2);

     for (int i = ; i <= n; i++) {

         for (int j = m; j; j--) {

             if (!a[i][j])    s2[i][j] = s2[i][j+] + ;//right

             else {

                 dp[i][j] = min(dp[i-][j+], min(s1[i-][j], s2[i][j+])) + ;

                 ans = max(ans, dp[i][j]);

             }

         }

     }

     printf("%d\n", ans);

     return ;

 }

而我自己做时……我这种满脑子二分前缀和的暴力分子大概没救了吧～不过这两种做法时间和空间上相差不多，反而是暴力快一点（逃

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int n, m, ans;

 int a[][], b[][], sum1[][], sum2[][], dp[][];

 void DP(int a[][], int sum[][]) {

     for (int i = ; i <= n; i++) {

         for (int j = ; j <= m; j++) {

             if (a[i][j]) {

                 auto ok = [](int i, int j, int tmp, int sum[][]) {

                     return  sum[i][j] - sum[i - tmp][j] - sum[i][j - tmp] + sum[i - tmp][j - tmp] == tmp;

                 };

                 int l = , r = dp[(i - )&][j - ] + , t;

                 while (l <= r) {

                     int mid = (l + r) >> ;

                     if (ok(i, j, mid, sum)) {

                         t = mid;

                         l = mid + ;

                     } else  r = mid - ;

                 }

                 dp[i&][j] = t;

             } else  dp[i&][j] = ;

             ans = max(ans, dp[i&][j]);

         }

     }

 }

 int main() {

     scanf("%d %d", &n, &m);

     for (int i = ; i <= n; i++)

         for (int j = ; j <= m; j++) {

             scanf("%d", &a[i][j]);

             b[i][m - j + ] = a[i][j];

         }

     for (int i = ; i <= n; i++)

         for (int j = ; j <= m; j++) {

             sum1[i][j] = sum1[i - ][j] + sum1[i][j - ] - sum1[i - ][j - ] + a[i][j];

             sum2[i][j] = sum2[i - ][j] + sum2[i][j - ] - sum2[i - ][j - ] + b[i][j];

         }

     DP(a, sum1);

     memset(dp, , sizeof dp);

     DP(b, sum2);

     printf("%d\n", ans);

     return ;

 }

巴特西

洛谷1736（二维dp+预处理）

最新文章

热门文章