powwow101   4년 전

https://www.acmicpc.net/board/...

정말 감사합니다. 도움 많이 받았습니다... 

코드 드러운건 이해해주시고...

코드 안봐도 사실 970까지 나오시는 분들은 어느 정도 따라오신 분들이실테니

저 같은 경우 dp[시작][끝] 으로 두고 dp[시작][끝] = dp[시작][부분 끝] + dp[부분 끝+1][끝] + 누적합(시작~끝) 

요렇게 점화식을 세웠는데 추가로 더해진 케이스가 부분 끝 = 시작이거나, 부분끝+1 = 끝 인 경우였습니다.

즉 테케2로 보자면 

3 4 5 에서 제 코드대로라면

  dp[3위치][5위치] = 7+ 5 + (3 + 4 + 5) = 24가 나오는데 

864가 나오기 위해서는

dp[3위치][5위치] = 7 + (3 + 4 + 5) = 19 가 나와야 합니다.

즉, 부분의 길이가 1이 되는 경우만 따로 잘 처리해주시면 잘 나올 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.