로곡 1387 2차원 dp는 특별히 간략한 문제가 아니에요.

2728 단어

낙곡1387


pp제목은 처음에 쓸 때 접두사와 검색을 사용했는데 복잡도는 대략 O(n^3)급이어서 이렇게 쓰는 것이 보급/향상-의 난이도에 비교적 부합된다고 생각합니다.나중에 문제풀이 구역의 신들의 문제풀이를 보고 mb를 시작하여 깨우침을 받았습니다.
dp[i][j]를 설정하면 (i, j)를 오른쪽 하단의 정사각형의 최대 변의 길이를 표시하고 전이 방정식은 다음과 같다.
dp[i][j] = min{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]} + 1 (a[i][j] == 1)
dp[i][j] = 0 (a[i][j] == 0)
이동은 매우 간단하지만 정확성은 뚜렷하지 않다. (i, j)를 오른쪽 하점으로 하는 정사각형을 고려하면 dp[i-1][j], dp[i][j-1], dp[i-1], dp[i-1][j-1] 세 개의 정사각형으로 제한된다. 그래서 이 정사각형은 세 개의 정사각형 중 가장 작은 것을 충족시킬 것이다. 합법성을 증명할 수 있고 합법성을 증명할 수 있다. 만약에 이때 고려한 정사각형의 길이가min()+1을 초과하면 반드시 삼정사각형 중 가장 작은 것과 충돌할 것이다.최우성을 증명할 수 있다.이로부터 방정식을 추측할 수 있다
#include 
#include 
#include 

const int maxn = 100 + 10;

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

int main () {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0) continue;
            dp[i][j] = std :: min(dp[i-1][j], dp[i][j-1]);
            dp[i][j] = std :: min(dp[i][j], dp[i-1][j-1]);
            dp[i][j]++;
        }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            if (ans < dp[i][j]) ans = dp[i][j];
    printf("%d", ans);
    return 0;
}
자가 치유 UI 테스트 자동화
[CSS] Flexbox, Display, Position

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage