'DP'에 해당되는 글 1건

  1. 2008/02/17 귀차니스트 Maximum Sum
◀ 이전페이지 1 다음페이지 ▶

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개, 댓글이 없습니다.

댓글을 달아 주세요

◀ 이전페이지 1 다음페이지 ▶