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

소스 코드

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#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");     } }