pppgod   1년 전

pichulia

http://codeforces.com/contest/426/problem/C

n개의 수열에서 수열의 내용을 k번 교환 가능하고, 임의에 i부터 j까지 수열의 합 중에서 가장 큰 값을 출력하는 문제입니다.

풀이랑 소스를 봤는데도 풀이법을 모르겠습니다.

설명 좀 해주실 수 있으신가요? ㅠ

august14   1년 전

K번 이하 횟수만큼 스왑하고 나서 답이 f(a,i,j)일 것이라고 가정합니다.

그러면 현재 a에서 f(a,i,j)를 한번 스왑하는 것으로 가장 좋게 발전시키는 방법은 (i,j)구간 내의 가장 작은 값과 (i,j)구간 밖의 가장 큰 값을 교환하는 것입니다. 이것을 K번까지 하면서 최댓값을 갱신하면 됩니다.

pppgod   1년 전

august14

답변해주셔서 감사합니다~

또 하나 배우고 갑니다...

baekjoon   1년 전

pichulia를 소환했는데 august14가 답변

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