777C Alyona and Spreadsheet

문제

• 링크 - http://codeforces.com/problemset/problem/777/C

문제 분류

• 난이도 - 중
• 태그 - dynamic programming

문제 풀이

2차원 배열 \(a[n][m] (0 \le n \cdot m \le 100,000)\)이 주어졌을때, 특정 행 구간 \([l, r]\)에 모든 원소가 non-decreasing order인 열이 하나라도 존재하는지 총 \(k (1 \le k \le 100,000)\)개의 구간에 대해 답을 계산해야 하는 문제다.

dp[ i ][ j ]를 j 번 열에서 i 번 행 이후로 연속적으로 non-decreasing order가 되는 원소의 개수라고 하면, 다음과 같은 식을 얻을 수 있다.

if ( a[ i ][ j ] <= a[ i+1 ][ j ] )

dp[ i ][ j ] = dp[ i+1 ][ j ] + 1

else

dp[ i ][ j ] = 1

소스 코드

#include <bits/stdc++.h> using namespace std; int main() { int n, m; scanf("%d%d", &n, &m); int a[n + 1][m + 1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &a[i][j]); } } int dp[n + 1][m + 1]; for (int j = 1; j <= m; j++) { dp[n][j] = 1; } for (int i = n - 1; i > 0; i--) { for (int j = 1; j <= m; j++) { if (a[i][j] <= a[i + 1][j]) { dp[i][j] = dp[i + 1][j] + 1; } else { dp[i][j] = 1; } } } int maxDp[n + 1] = { 0 }; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { maxDp[i] = max(maxDp[i], dp[i][j]); } } int k; scanf("%d", &k); for (int i = 0; i < k; i++) { int l, r; scanf("%d%d", &l, &r); if (maxDp[l] >= r - l + 1) printf("Yes\n"); else printf("No\n"); } }