Posted in日常

P1387-最大正方形

2024年4月17日

题目传送门

点我

题目思路

打dp，第一次的思路是当前格子为1，且上和左都是1，那么就左上角的值+1保存为当前值。

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m, 0));
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> v[i][j];
    int ans = 0;
    for (int i = 1; i < n; i++)
        dp[i][0] = v[i][0];
    for (int i = 1; i < m; i++)
        dp[0][i] = v[0][i];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = v[i][j] ? (v[i - 1][j] * v[i][j - 1] ? dp[i - 1][j - 1] + 1 : 1) : 0;
            if (dp[i][j] > ans)
                ans = dp[i][j];
        }
    cout << ans << endl;
    return 0;
}

很遗憾，不对，但是过了三个点，说明有情况是适用的，说明考虑不全面

考虑的是有问题的，因为dp[i][j]代表的是往左和上有几个连续的1，那么不应该只考虑dp[i-1][j-1]，还要考虑左边和右边，取三个值的最小值，就代表了当前格子往左和上最小的连续1的个数，然后如果当前为1加1即可，不然为0

AC代码

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> v(n, vector<int>(m, 0));
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> v[i][j];
    int ans = 0;
    for (int i = 1; i < n; i++)
        dp[i][0] = v[i][0];
    for (int i = 1; i < m; i++)
        dp[0][i] = v[0][i];
    for (int i = 1; i < n; i++)
        for (int j = 1; j < m; j++)
        {
            dp[i][j] = v[i][j] ? min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1 : 0;
            if (dp[i][j] > ans)
                ans = dp[i][j];
        }
    cout << ans << endl;
    return 0;
}
Tags: