블로그는 귀차니즘

First Sensation
  • 공지
  • 지역로그
  • 태그
  • 방명록

Maximum Sum

Algorithm 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>
    2.  
    3. using namespace std;
    4.  
    5. short Matrix[ 101 ][ 101 ][ 101 ][ 101 ] = { 0, };
    6.  
    7. int main( int argc, char **argv )
    8. {
    9.     int MaxSum = -999999;
    10.     int size;
    11.  
    12.     cin >> size;
    13.  
    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.     }
    19.  
    20.     for( int StartI = 1; StartI <= size; StartI++ ) {
    21.         for( int StartJ = 1; StartJ <= size; StartJ++ ) {
    22.  
    23.             for( int EndI = StartI; EndI <= size; EndI++ ) {
    24.                 for( int EndJ = StartJ; EndJ <= size; EndJ++ ) {
    25.  
    26.                     short RectangleSum = Matrix[ StartI ][ StartJ ][ EndI ][ EndJ - 1 ];
    27.                     short LineSum = Matrix[ StartI ][ EndJ ][ EndI - 1 ][ EndJ ];
    28.  
    29.                     short NewLineSum = LineSum + Matrix[ EndI ][ EndJ ][ EndI ][ EndJ ];
    30.                     Matrix[ StartI ][ EndJ ][ EndI ][ EndJ ] = NewLineSum;
    31.  
    32.                     short NewRectangleSum = RectangleSum + NewLineSum;
    33.                     Matrix[ StartI ][ StartJ ][ EndI ][ EndJ ] = NewRectangleSum;
    34.  
    35.                     if( MaxSum < NewRectangleSum )
    36.                         MaxSum = NewRectangleSum;
    37.                 }
    38.             } 
    39.  
    40.         }
    41.     }
    42.  
    43.     cout << MaxSum;
    44.  
    45.     return 0;
    46. }
    47.  

크리에이티브 커먼즈 라이센스
Creative Commons License
이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

"Algorithm" 분류의 다른 글

Algorithm Traning Book - 다섯번째 문제 (0)2008/06/15
Algorithm Traning Book - 세 번째 문제 (0)2008/06/10
Algorithm Traning Book - 두 번째 문제 (0)2008/06/09
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 ACM, ACM-ICPC, C++, DP, Dynamic Programming
트랙백은 하나, 댓글이 없습니다.

트랙백 주소 :: 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+..

댓글을 달아 주세요

◀ 이전페이지 1 ... 109 110 111 112 113 114 115 116 117 ... 118 다음페이지 ▶
블로그 이미지
First Sensation 귀차니스트
rss
  • 관리자
  • 글쓰기

카테고리

  • 전체 (118)
    • Computer (3)
    • Language (14)
    • Reverse Engineering (1)
    • Algorithm (9)
    • TopCoder (3)
    • Library (2)
    • Programming (21)
    • Programming Tip (9)
    • PSP-Programming (10)
    • Program (5)
    • Small Talk (33)
    • Document (4)
    • OS Develope (4)

최근에 올라온 글

  • Script Interpreter - b....
  • VirtualHttpServer - 가.... (2)
  • 음.. 여러가지 일이 있.... (2)
  • 어후.. 드디어 인터럽트....
  • Kernel Image에 어이없....

최근에 달린 댓글

  • 헠 ㅋ 다음에도 들러주세용 ㅋㅋ. 귀차니스트 03/09
  • ㅎㅎ RSS로 첨 온 글이네.ㅋ. 당구리 02/22
  • 음.. 한글화 파일 0.5 버젼은.... 귀차니스트 02/22
  • 관리자만 볼 수 있는 댓글입.... 비밀방문자 01/30
  • 어떤 의미이신지 잘 모르겠네.... 귀차니스트 01/23

달력

«   2010/03   »
일 월 화 수 목 금 토
  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      

링크

  • kkamagui 프로그래밍 세상.
  • runner님의 이글루.
  • 당구리의 마굿간.
  • 동우fly.
  • 류광의 번역 이야기.
  • 서광열의 프로그래밍 언....
  • 준호씨의 블로그.
  • 최익필의 이름없는 블로그.
  • 위키는 귀차니즘.

최근에 받은 트랙백

  • 한게임 테트리스 인공지.... 고니's Life 2009
  • ACM 706 (Uva ID) : LCD.... 알고리즘 트레이닝 : Oh... 2009
  • 문제 4 : LCD 디스플레.... 최익필의 이름없는 블로그 2009
  • 궁극의 예외처리. 이름없는 블로그 2008
  • Maximum sum. 티스토리 지점 2008

글 보관함

  • 2010/03 (1)
  • 2010/02 (1)
  • 2010/01 (1)
  • 2009/12 (3)
  • 2009/08 (1)

태그목록

  • Secure
  • Call By Reference
  • RLE8
  • 한국가상캠퍼스
  • OS
  • 갑
  • 파티션
  • Warcraft III
  • 6GB
  • 디아블로3
  • 상속
  • 어쌔신 크리드
  • 디자인패턴
  • C++
  • 클라리넷
  • PlugInOS
  • Freetype2
  • 병렬
  • 프로토타입
  • C#
  • Develope
  • HTML 파서
  • Bootloader
  • Mine Sweeper
  • 보안
  • Pangya
  • VCL
  • 수학
  • QT4
  • Directive
지역로그 : 태그 : 방명록 : 관리자 : 글쓰기
귀차니스트’s Blog is powered by Textcube 1.7.5 : Risoluto / Designed by DesignNia.net