Maximum Sum

Algorithm/Acm 2008/02/17 08:30 귀차니스트
  1. 문제링크 : http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
  2.  의   견   : Dynamic Programming을 배웠고, 사용한다면 쉬운 문제, 하지만 단순히 for 루프를 이용하여 6중 for 루프를 사용한다면 time exceed를 면할 수 없을 것입니다.
    DP 방법은 배열을 사용할 때 [ 시작 x 인덱스 ][ 시작 y 인덱스 ][ 끝 x 인덱스 ][ 끝 y 인덱스 ]로 의미를 부여하여 대상 값들을 계산 후 업데이트하고 재사용합니다.
  3. 소스
    108.cpp (Language : cpp)
    1. #include <iostream>
    3. using namespace std;
    5. short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
    7. int main( int argc, char **argv )
    8. {
    9.     int MaxSum = -999999;
    10.     int size;
    12.     cin >> size;
    14.     for( int i = 1; i <= size; i++ ) {
    15.         for( int j = 1; j <= size; j++ ) {
    16.             cin >> Matrix[ i ][ j ][ i ][ j ];
    17.         }
    18.     }
    20.     for( int StartI = 1; StartI <= size; StartI++ ) {
    21.         for( int StartJ = 1; StartJ <= size; StartJ++ ) {
    23.             for( int EndI = StartI; EndI <= size; EndI++ ) {
    24.                 for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
    26.                     short RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
    27.                     short LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
    29.                     short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
    30.                     Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
    32.                     short NewRectangleSum = RectangleSum + NewLineSum;
    33.                     Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
    35.                     if( MaxSum < NewRectangleSum )
    36.                         MaxSum = NewRectangleSum;
    37.                 }
    38.             }
    40.         }
    41.     }
    43.     cout << MaxSum;
    45.     return 0;
    46. }

크리에이티브 커먼즈 라이센스
Creative Commons License

"Algorithm / Acm" 분류의 다른 글

LCD Display (3)2008/02/17
The Skyline Problem (2)2008/02/17
Ecological Bin Packing (0)2008/02/17
3n+1 Problem (0)2008/02/17
The Blocks Problem (0)2008/02/17
2008/02/17 08:30 2008/02/17 08:30
TAG , , , ,
트랙백 2개, 댓글이 없습니다.

트랙백 주소 :: http://www.filewiki.net/tc/trackback/6

  1. Subject: Maximum sum

    Tracked from 티스토리 지점 2008/04/09 14:22  삭제

    문제 페이지 귀차니스트 님이 푸신 답을 조금 개선해 봤다. 자동채점 기준으로 수행 시간이 0.4초 정도 줄었다. #include <stdio.h> short m[101][101][101][101]={}; int main(void) { int rsum, lsum, nrsm, nlsm; int si, sj, ei, ej, size,i,j; int maxsum = -2000000; scanf("%d", &size); for (i=1; i<=size; i+..

  2. Subject: Fioricet used for.

    Tracked from Fioricet used for. 2010/09/04 03:11  삭제

    Fioricet used for.

댓글을 달아 주세요

◀ 이전페이지 1 ... 114 115 116 117 118 119 120 121 122 ... 123 다음페이지 ▶